# 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](https://leetcode.com/problems/longest-harmonious-subsequence/), [github.com](https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0594.Longest%20Harmonious%20Subsequence/README_EN.md))

## Input and Output

| Item | Meaning |
|---|---|
| `nums` | Integer array |
| Output | Length of the longest harmonious subsequence |
| Harmonious condition | `max(subsequence) - min(subsequence) == 1` |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
5
```

The longest harmonious subsequence is:

```python
[3, 2, 2, 2, 3]
```

Its maximum is `3`.

Its minimum is `2`.

The difference is:

```text
3 - 2 = 1
```

So its length is `5`.

Example 2:

```python
nums = [1, 2, 3, 4]
```

Output:

```python
2
```

Possible harmonious subsequences include:

```python
[1, 2]
[2, 3]
[3, 4]
```

Each has length `2`.

Example 3:

```python
nums = [1, 1, 1, 1]
```

Output:

```python
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:

```text
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:

```text
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:

```text
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + k)` | Count all numbers, then scan distinct values |
| Space | `O(k)` | Store one count per distinct value |

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

## Implementation

```python
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:

```python
count = Counter(nums)
```

For example:

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

gives:

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

We start with no valid subsequence:

```python
answer = 0
```

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

```python
if x + 1 in count:
```

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

```python
count[x] + count[x + 1]
```

We keep the largest such length:

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

Finally:

```python
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.

```python
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

```python
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:

| Test | Why |
|---|---|
| `[1, 3, 2, 2, 5, 2, 3, 7]` | Main sample |
| `[1, 2, 3, 4]` | Multiple valid pairs with same length |
| `[1, 1, 1, 1]` | No pair differs by `1` |
| `[1, 1, 2, 2, 2]` | Use all occurrences of two values |
| Negative numbers | Consecutive values can be negative |
| Single element | Cannot form max-min difference `1` |