# 594 Longest Harmonious Subsequence

We define a harmonious array is an array where the difference between its maximum value and its minimum value is **exactly**1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible [subsequences](https://en.wikipedia.org/wiki/Subsequence).

**Example 1:**

```
Input:
 [1,3,2,2,5,2,3,7]

Output:
 5

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

**Note:**The length of the input array will not exceed 20,000.

**The Idea:** The first thing to understand is that if the maximum - minimum value of a subsequence is 1, then that subsequence can only contain values of the maximum and/or minimum since every other number above or below these would break the definition. So for every number in the array, we only need to keep track of a count of two things: a count of the number itself (which will serve as the minimum), and a count of the number greater than itself (which will serve as the maximum). Together, these will make up some subsequence in the input array.

**Complexity:** O(N) time and space

```python
from collections import Counter


class Solution:
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        hist = Counter(nums)
        maxx = 0
        for key, _ in hist.items():
            if key + 1 in hist:
                maxx = max(maxx, hist[key] + hist[key + 1])
        return maxx
```