Problem Description

A harmonious array is defined as an array where the difference between its maximum value and its minimum value is exactly 1.

Given an integer array nums, you need to find the length of the longest harmonious subsequence among all possible subsequences.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. For example, if nums = [1, 3, 2, 2, 5, 2, 3, 7], then [3, 2, 2, 2, 3] is a valid subsequence where the minimum value is 2 and maximum value is 3, making it harmonious since 3 - 2 = 1.

The solution uses a hash table to count the frequency of each number in the array. For each number x in the hash table, if x + 1 also exists, then all occurrences of x and x + 1 together form a harmonious subsequence. The algorithm finds the maximum sum of counts for such pairs (x, x+1) to determine the longest harmonious subsequence.

Intuition

To find the longest harmonious subsequence, we need to identify which elements from the array can form a valid harmonious group. Since a harmonious array must have exactly a difference of 1 between its maximum and minimum values, this means our subsequence can only contain two distinct values that differ by 1.

The key insight is that if we want to maximize the length of our harmonious subsequence, we should include all occurrences of two consecutive numbers (like all 2s and all 3s). Why? Because:

• We can only use at most two distinct values (otherwise the difference between max and min would exceed 1)
• These two values must be consecutive integers (to maintain the difference of exactly 1)
• To maximize length, we want to include every occurrence of both chosen values

This leads us to think about counting frequencies. If we know that the array contains a occurrences of number x and b occurrences of number x+1, then we can form a harmonious subsequence of length a + b using all these elements.

Therefore, the problem reduces to:

1. Count the frequency of each number in the array
2. For each number x, check if x+1 exists in the array
3. If both exist, calculate count(x) + count(x+1)
4. Return the maximum sum found

This approach works because we're essentially trying all possible pairs of consecutive numbers and selecting the pair that gives us the longest subsequence.

Learn more about Sorting and Sliding Window patterns.

Solution Approach

The solution uses a hash table to efficiently count and lookup element frequencies.

Step 1: Count Element Frequencies

We use Python's Counter from the collections module to create a hash table cnt that stores the frequency of each element in nums. This gives us a mapping where cnt[x] represents how many times the value x appears in the array.

Step 2: Find All Valid Harmonious Pairs

We iterate through each key-value pair (x, c) in the hash table, where:

• x is a unique number from the array
• c is the count of occurrences of x

For each number x, we check if x + 1 exists in the hash table by evaluating cnt[x + 1]. If it exists (meaning it has a non-zero count), then we can form a harmonious subsequence using all occurrences of both x and x + 1.

Step 3: Calculate Maximum Length

The length of a harmonious subsequence formed by numbers x and x + 1 is simply c + cnt[x + 1], which represents the total count of both values.

We use a generator expression (c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]) to calculate the lengths of all possible harmonious subsequences. The condition if cnt[x + 1] filters out cases where x + 1 doesn't exist in the array (would have a count of 0).

Step 4: Return the Result

The max() function finds the maximum length among all valid harmonious subsequences. The default=0 parameter handles the edge case where no harmonious subsequence exists (for example, when all elements in the array are the same or when no two consecutive integers exist).

The time complexity is O(n) where n is the length of the array, as we iterate through the array once to build the counter and then iterate through the unique elements once. The space complexity is also O(n) for storing the hash table.

Example Walkthrough

Let's walk through the solution with nums = [1, 3, 2, 2, 5, 2, 3, 7].

Step 1: Count Element Frequencies

First, we create a frequency map of all elements:

• 1 appears 1 time
• 2 appears 3 times
• 3 appears 2 times
• 5 appears 1 time
• 7 appears 1 time

So our hash table looks like: {1: 1, 2: 3, 3: 2, 5: 1, 7: 1}

Step 2: Check Each Number for Valid Pairs

Now we examine each number x to see if x + 1 exists:

• For x = 1: Check if 2 exists → YES!

  • Harmonious subsequence using all 1s and 2s: [1, 2, 2, 2]
  • Length = 1 + 3 = 4

• For x = 2: Check if 3 exists → YES!

  • Harmonious subsequence using all 2s and 3s: [2, 2, 2, 3, 3]
  • Length = 3 + 2 = 5

• For x = 3: Check if 4 exists → NO

  • Cannot form a harmonious subsequence

• For x = 5: Check if 6 exists → NO

  • Cannot form a harmonious subsequence

• For x = 7: Check if 8 exists → NO

  • Cannot form a harmonious subsequence

Step 3: Find Maximum Length

From our valid pairs:

• Pair (1, 2): length = 4
• Pair (2, 3): length = 5

The maximum length is 5.

Therefore, the longest harmonious subsequence has length 5, consisting of all the 2s and 3s from the original array: [3, 2, 2, 2, 3].

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Creating the Counter object requires iterating through all n elements once: O(n)
• The generator expression iterates through all unique elements in the Counter (at most n elements), and for each element, it performs constant time operations (dictionary lookups and addition): O(n)
• The max function iterates through the generator results: O(n)
• Overall: O(n) + O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the array nums. This is because:

• The Counter object stores at most n key-value pairs (in the worst case where all elements are unique): O(n)
• The generator expression doesn't create an additional list but processes elements one at a time: O(1) additional space
• Overall: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Subsequence vs Subarray

A common mistake is confusing a subsequence with a subarray. Students often think they need to find contiguous elements that form a harmonious array. This leads to incorrect sliding window approaches or attempts to maintain order while checking adjacent elements.

Incorrect approach:

# Wrong: Trying to find contiguous harmonious subarray
def findLHS_wrong(nums):
    max_length = 0
    for i in range(len(nums)):
        for j in range(i+1, len(nums)+1):
            subarray = nums[i:j]
            if max(subarray) - min(subarray) == 1:
                max_length = max(max_length, len(subarray))
    return max_length

Why it's wrong: This looks for contiguous subarrays, but the problem asks for subsequences which don't need to be contiguous. For example, in [1,3,2,2,5,2,3,7], the elements [3,2,2,2,3] form a valid harmonious subsequence even though they're not consecutive in the original array.

Pitfall 2: Including More Than Two Distinct Values

Another mistake is trying to include multiple values that form a range, rather than exactly two consecutive integers.

Incorrect approach:

# Wrong: Trying to include multiple consecutive values
def findLHS_wrong(nums):
    frequency_map = Counter(nums)
    max_length = 0
  
    for number in frequency_map:
        # Wrong: checking if we can form a range
        current_length = frequency_map[number]
        if number - 1 in frequency_map:
            current_length += frequency_map[number - 1]
        if number + 1 in frequency_map:
            current_length += frequency_map[number + 1]
        max_length = max(max_length, current_length)
  
    return max_length

Why it's wrong: This might count three distinct values (number-1, number, number+1), but a harmonious array must have exactly a difference of 1 between max and min, meaning only two consecutive values are allowed.

Pitfall 3: Checking Both Directions Redundantly

Some solutions check both x+1 and x-1 for each number, leading to counting the same pair twice.

Incorrect approach:

# Wrong: Double counting pairs
def findLHS_wrong(nums):
    frequency_map = Counter(nums)
    max_length = 0
  
    for number, count in frequency_map.items():
        # Checking both directions causes double counting
        if number + 1 in frequency_map:
            max_length = max(max_length, count + frequency_map[number + 1])
        if number - 1 in frequency_map:
            max_length = max(max_length, count + frequency_map[number - 1])
  
    return max_length

Why it's problematic: While this gives the correct answer, it's inefficient because each pair (x, x+1) is evaluated twice - once when processing x and once when processing x+1. The solution only needs to check in one direction.

Correct Solution Reminder

The key insights for the correct solution are:

1. A harmonious subsequence contains exactly two distinct consecutive integers
2. Order doesn't matter - we just need counts
3. Checking only x+1 for each x is sufficient to find all pairs
4. The length is simply the sum of frequencies of the two consecutive numbers