Longest Harmonious Subsequence

• LeetCode: Longest Harmonious Subsequence

• Problem:

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.

• Note:

The length of the input array will not exceed 20,000.

• Example:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

• Analysis:

I. Array sort

Because subsequence is out of order, we can sort the input array first. 

And the, use two pointers to find the longest subarray is harmonious.

II. HashMap

• Array Sort:

• Code - Java:

class Solution {
    public int findLHS(int[] nums) {
        int len = nums.length;
        int left = 0;
        int result = 0;
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            while (left < i && nums[i] - nums[left] > 1L) {
                left++;
            }
            if (nums[i] - nums[left] == 1L) {
                result = Math.max(i - left + 1, result);
            }
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    int findLHS(vector<int>& nums) {
        int len = nums.size();
        int left = 0;
        int result = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < len; i++) {
            while (left < i && nums[i] - nums[left] > 1L) {
                left++;
            }
            if (nums[i] - nums[left] == 1L) {
                result = max(i - left + 1, result);
            }
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numsLen, left, result = len(nums), 0, 0
        nums = sorted(nums)
        for i in range(numsLen):
            while left < i and nums[i] - nums[left] > 1L:
                left += 1
            if nums[i] - nums[left] == 1L:
                result = max(i - left + 1, result)
        return result

• HashMap:

• Code - Java:

class Solution {
    public int findLHS(int[] nums) {
        int len = nums.length;
        int result = 0;
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++) {
            int count = counts.getOrDefault(nums[i], 0) + 1;
            counts.put(nums[i], count);
            int dec = counts.getOrDefault(nums[i] - 1, 0);
            int inc = counts.getOrDefault(nums[i] + 1, 0);
            result = dec != 0 ? Math.max(result, count + dec) : result;
            result = inc != 0 ? Math.max(result, count + inc) : result;
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    int findLHS(vector<int>& nums) {
        int len = nums.size();
        int result = 0;
        map<int, int> counts;
        for (int i = 0; i < len; i++) {
            if (counts.find(nums[i]) != counts.end()) {
                counts[nums[i]] += 1;
            } else {
                counts.insert(pair<int, int>(nums[i], 1));
            }
            int inc = nums[i] + 1;
            if (counts.find(inc) != counts.end()) {
                result = max(result, counts[nums[i]] + counts[inc]);
            }
            int dec = nums[i] - 1;
            if (counts.find(dec) != counts.end()) {
                result = max(result, counts[nums[i]] + counts[dec]);
            }
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numsLen, result = len(nums), 0
        counts = {}
        for val in nums:
            if val in counts:
                counts[val] += 1
            else:
                counts[val] = 1
            inc = val + 1
            dec = val - 1
            if dec in counts:
                result = max(result, counts[val] + counts[dec])
            if inc in counts:
                result = max(result, counts[val] + counts[inc])
        return result

• Array Sort:

• Time Complexity: O(NLOGN), N is the length of the input array

• Space Complexity: O(1)

• HashMap:

• Time Complexity: O(N), N is the length of the input array

• Space Complexity: O(N), N is the length of the input array