Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A harmonious subsequence contains exactly two distinct integer values, x and x + 1, with both present. Because this is a subsequence rather than a contiguous subarray, we can keep every occurrence of those two values in its original order. Their combined frequency is therefore the best answer for that pair.

Approach

Count the frequency of each value in a hash map.
For each distinct x, check whether x + 1 is also present. If so, compare their combined count with the current maximum.
Return the maximum, initially zero. Requiring the second value to exist is essential: a sequence containing only equal values has difference zero, not one.

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        n = len(nums)
        map = defaultdict(int)

        for x in nums:
            map[x] += 1

        res = 0

        for k in map:
            if k + 1 in map:
                res = max(res, map[k] + map[k + 1])

        return res

Complexity analysis

For n values and u distinct values, the two hash-map passes take O(n + u) time and O(u) auxiliary space.