Longest Harmonious Subsequence

Even if we were to use a hash-map, since we want to iterate through all the keys in order, that implies that we will still have to sort nums.

Therefore, we should just sort nums first, and then simply run a two-pointers solution, with:

• l pointing at nums[l]
• r pointing at nums[r]

Then if nums[l] + 1 == nums[r], then we can update our ans if r-l+1 is larger.

code

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int curr = nums[0];
        int l = 0, r = 0, ans = 0;
        while (r < nums.size()-1)
        {
            if(nums[r+1] > nums[l] + 1)
            {
                if (nums[r] == nums[l]+1)
                {
                    ans = max(r-l+1, ans);
                }
                while(l <= r && nums[l] != nums[r])
                {
                    ++l;
                }
            }
            ++r;
        }
        if (nums[r] == nums[l]+1)
        {
            ans = max(r-l+1, ans);
        }
        return ans;
    }
};

complexity

• Time: O(n log(n))
• Space: O(1)