Longest Harmonious Subsequence

Problem Statement

In the task, a "harmonious array" is characterized specifically as one where the maximum and minimum values have a precise difference of 1. From a given integer array nums, the challenge is to determine the length of the longest harmonious subsequence that can be derived from possible subsequences within the array. A subsequence is a sequence derived from another sequence where elements are picked without changing their original order, but not necessarily consecutively. The solution must efficiently dig through permutations to spot this highest-scoring harmonious subsequence.

Examples

Example 1

Input:

nums = [1,3,2,2,5,2,3,7]

Output:

5

Explanation:

The longest harmonious subsequence is `[3,2,2,2,3]`.

Example 2

Input:

nums = [1,2,3,4]

Output:

2

Explanation:

The longest harmonious subsequences are `[1,2]`, `[2,3]`, and `[3,4]`, all of which have a length of 2.

Example 3

Input:

nums = [1,1,1,1]

Output:

0

Explanation:

No harmonic subsequence exists.

Constraints

• 1 <= nums.length <= 2 * 104
• -109 <= nums[i] <= 109

Approach and Intuition

The primary intuition to solve this problem lies in identifying and counting elements that form potential pairs (difference of 1) and then determining the most numerous occurrence of such pairs in the given list. The steps mentioned below outline a conceptual approach:

1. First, compute the frequency of each number in the array using a hashmap or a dictionary.
2. After building the frequency dictionary, the next step is to iterate through all unique numbers seen.
3. For each number, check if the number +1 exists in the dictionary.
4. If both the number and the number +1 are in the dictionary, calculate the combined length of these numbers from their frequencies.
5. Track the maximum combined length during the iteration.
6. This maximum value depicts the length of the longest harmonious subsequence.

Let's break down the thought process through the examples provided:

• Example 1: Looking at the array [1,3,2,2,5,2,3,7], 2 and 3 appear multiple times and are consecutive integers. Therefore, the longest subsequence combining these would be [3,2,2,2,3], having the length of 5.
• Example 2: In the array [1,2,3,4], possible consecutive integer pairs are [1,2], [2,3], and [3,4], each of length 2. No pair exceeds the length of 2, hence the answer is 2.
• Example 3: The array [1,1,1,1] contains no harmonious subsequences as it does not have two different numbers that are consecutive integers. Hence, the result is 0.

Following this approach allows for a structured way to determine the optimal solution within the constraints stipulated, ensuring efficiency and clarity in the process.

Solutions

public class Solution {
    public int longestHarmoniousSubsequence(int[] elements) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        int longestLength = 0;
        for (int value : elements) {
            frequencyMap.put(value, frequencyMap.getOrDefault(value, 0) + 1);
            if (frequencyMap.containsKey(value + 1))
                longestLength = Math.max(longestLength, frequencyMap.get(value) + frequencyMap.get(value + 1));
            if (frequencyMap.containsKey(value - 1))
                longestLength = Math.max(longestLength, frequencyMap.get(value) + frequencyMap.get(value - 1));
        }
        return longestLength;
    }
}