LeetCode 594: Longest Harmonious Subsequence

Problem Restatement

We are given an integer array nums.

A harmonious subsequence is a subsequence where the difference between the maximum value and the minimum value is exactly 1.

We need to return the length of the longest harmonious subsequence.

A subsequence is formed by deleting some elements, possibly none, without changing the order of the remaining elements. The elements do not need to be contiguous.

The constraints are 1 <= nums.length <= 2 * 10^4 and -10^9 <= nums[i] <= 10^9. (leetcode.com, github.com)

Input and Output

Example function shape:

def findLHS(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

Output:

5

The longest harmonious subsequence is:

[3, 2, 2, 2, 3]

Its maximum is 3.

Its minimum is 2.

The difference is:

3 - 2 = 1

So its length is 5.

Example 2:

nums = [1, 2, 3, 4]

Output:

2

Possible harmonious subsequences include:

[1, 2]
[2, 3]
[3, 4]

Each has length 2.

Example 3:

nums = [1, 1, 1, 1]

Output:

0

There is no subsequence whose maximum and minimum differ by exactly 1.

First Thought: Try Every Subsequence

A brute force solution could generate every subsequence and test whether it is harmonious.

But an array of length n has:

2^n

subsequences.

Since n can be 20000, this is impossible.

We need to use the structure of the harmonious condition.

Key Insight

If a subsequence is harmonious, then its maximum and minimum differ by exactly 1.

That means the subsequence can only use values like:

x and x + 1

It cannot contain x, x + 1, and x + 2, because then the maximum and minimum would differ by 2.

So for every value x, the best harmonious subsequence using values x and x + 1 has length:

count[x] + count[x + 1]

Because subsequences do not need to be contiguous, we can take all occurrences of both values from the array.

So the problem becomes:

1. Count how many times each number appears.
2. For each number x, check whether x + 1 exists.
3. Maximize count[x] + count[x + 1].

Algorithm

1. Count the frequency of every number in nums.
2. Initialize answer = 0.
3. For each number x in the frequency map:
   • If x + 1 exists:
     • Compute count[x] + count[x + 1].
     • Update answer.
4. Return answer.

Correctness

Every harmonious subsequence has maximum and minimum values that differ by exactly 1. Therefore, if its minimum value is x, its maximum value must be x + 1. The subsequence can contain only these two values.

For any pair (x, x + 1) that exists in the array, the longest harmonious subsequence using that pair includes every occurrence of x and every occurrence of x + 1. Since we are forming a subsequence, not a contiguous subarray, keeping all such occurrences is always allowed and preserves their original order.

The algorithm checks every possible pair (x, x + 1) by iterating over all distinct values x. For each valid pair, it computes exactly the maximum possible length for that pair. Taking the maximum over all pairs gives the length of the longest harmonious subsequence.

If no such pair exists, no harmonious subsequence exists, and the algorithm correctly returns 0.

Complexity

Let:

n = len(nums)
k = number of distinct values

Since k <= n, the time complexity is O(n) and the space complexity is O(n).

Implementation

from collections import Counter

class Solution:
    def findLHS(self, nums: list[int]) -> int:
        count = Counter(nums)
        answer = 0

        for x in count:
            if x + 1 in count:
                answer = max(answer, count[x] + count[x + 1])

        return answer

Code Explanation

This counts every value:

count = Counter(nums)

For example:

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

gives:

{
    1: 1,
    2: 3,
    3: 2,
    5: 1,
    7: 1
}

We start with no valid subsequence:

answer = 0

Then for each number x, we check whether x + 1 exists:

if x + 1 in count:

If it exists, then all occurrences of x and x + 1 form a harmonious subsequence:

count[x] + count[x + 1]

We keep the largest such length:

answer = max(answer, count[x] + count[x + 1])

Finally:

return answer

returns 0 if no valid pair was found.

Sorting Alternative

We can also sort the array and use a sliding window.

After sorting, all equal values are grouped together. We keep a window whose maximum and minimum differ by at most 1.

When the difference is exactly 1, the window is harmonious.

class Solution:
    def findLHS(self, nums: list[int]) -> int:
        nums.sort()

        left = 0
        answer = 0

        for right in range(len(nums)):
            while nums[right] - nums[left] > 1:
                left += 1

            if nums[right] - nums[left] == 1:
                answer = max(answer, right - left + 1)

        return answer

This version uses O(n log n) time because of sorting and O(1) extra space if sorting in place is allowed.

Testing

def run_tests():
    s = Solution()

    assert s.findLHS([1, 3, 2, 2, 5, 2, 3, 7]) == 5
    assert s.findLHS([1, 2, 3, 4]) == 2
    assert s.findLHS([1, 1, 1, 1]) == 0
    assert s.findLHS([1, 1, 2, 2, 2]) == 5
    assert s.findLHS([-1, -2, -2, -1, 0]) == 4
    assert s.findLHS([10]) == 0

    print("all tests passed")

run_tests()

Test meaning: