Longest Harmonious Subsequence

Intuition

• What tripped me up about this problem is that you are dealing with a Subsequence. That specifically means that you can sort. Why can you sort? This is because:

Info

Yes, a subsequence typically does preserve the order of elements from the original sequence. However, this problem doesn’t require that order be maintained for the subsequence. This is because the harmonious property is based solely on the values of the elements, not their order.

A subsequence is just a sequence that can be derived from another sequence by deleting some (or no) elements, without changing the order of the remaining elements. But in this problem, we’re interested in the length of the longest harmonious subsequence, and the length would be the same regardless of the order in which the elements appear.

So, while we’re technically counting combinations of elements that could form such subsequences, it doesn’t affect the solution to this problem. This is because we’re ultimately only interested in the maximum length of such subsequences, not the subsequences themselves. So even though we are not explicitly forming these subsequences, our approach correctly calculates the maximum possible length for such a subsequence.

• I was trying to form the subsequences themselves which is why this problem took a long time.

Runtime

$O(NlogN)$ if sorted, and $O(N)$ with hashmap (since that’s all you are using).

Code

Without Sorting (Counter)

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        d = Counter(nums)
        max_count = 0
        for num in d:
            if d[num + 1]:
                max_count = max(max_count, d[num] + d[num + 1])
        return max_count

With Sorting

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums.sort()
        d = Counter()
        left = 0
        max_counter = 0
        for right in range(len(nums)):
            d[nums[right]] += 1
            if nums[right] > nums[left] + 1:
                while left < right \
                    and nums[left] != nums[right] - 1:
                    d[nums[left]] -= 1
                    if d[nums[left]] == 0:
                        del d[nums[left]]
                    left += 1
            
            if len(d) == 2:
                max_counter = max(max_counter, right - left + 1)
 
        return max_counter

Notes

---

References

https://leetcode.com/problems/longest-harmonious-subsequence/