> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/594-longest-harmonious-subsequence.md).

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