[Leetcode] 594. Longest Harmonious Subsequence

https://leetcode.com/problems/longest-harmonious-subsequence/?envType=daily-question&envId=2025-06-30

initial

we can turn it into counter and check key+1 and key-1 for each key. BUT that means we can check keys multiple times, which might not be efficient.

Actually if we just sort the keys, then for each current key, we can check key+1 and no need to check key-1 cuz its sorted. We would have checked the previous key-1 if we can form a valid pair with key

sol

be careful with sorted() and counter. sorted() returns a list, not the original counter. So if u sort via keys, it returns a list of keys.

from collections import Counter
class Solution:
    def findLHS(self, nums: List[int]) -> int:
        counter = Counter(nums)
        keys = sorted(counter.keys())
        ans=0
        for key in keys:
            if key+1 in counter:
                ans=max(ans,counter[key]+ counter[key+1])
        return ans

complexity

turning into counter takes o(n) time?
space is number of unique keys

yes