594 Longest Harmonious Subsequence

1. Description

We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1. Given an integer aray nums, return the length of its longest harmonious subsequence among all its possible subsequences. 

 

A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. 

 

constraints :

• 1 <= nums.length <= 2 * \(10^{4}\) 
• \(-10^{9}\) <= nums[i] <= \(10^{9}\)

 

2. Algorithms

Let's see when we get [1, 3, 2, 2, 5, 2, 3, 7] as input. Because a harmonious array is the difference between its maximum value and its minimum value is eactly 1, we sort the input array and compare from index 0 and len(nums) - 1.

 

After sorting the list, the we will get [1, 2, 2, 2, 3, 3, 5, 7]. If we use brute force algorithm, we have to iterate through the list with \(O(N^2)\). So we set two pointers i and j which i starts from the 0 and j starts from len(nums) - 1. 

 

If the difference of corresponding values of i and j is exactly 1, then we compare previous max length with current length. 

After comparing task is over, then we increment i by 1 and reset j as len(num) - 1. All repeated works will be done if i become len(nums) - 1.

 

1. Start
2. Sort the input list in increasing order. 
3. Declare two variables named i and max_length. 
4. Initialized them to 0.
5. Repeat the steps until i == len(nums) . 
   1. Reset j as len(nums) - 1.
   2. Repeat the steps until j === i and nums[j] - nums[i] == 1. 
      1. Increment j by -1. 
   3. Update max value between max_length and current length(j - i + 1).
   4. Increment i by 1. 
6. Return max_length. 
7. End 

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        # Sort the list in increasing order
        nums = sorted(nums) 
        i, max_length = 0, 0
        
        while i < len(nums) - 1 : 
            j = len(nums) - 1
            while (j > i) and (nums[j] - nums[i] != 1) : 
                j -= 1
            length = j - i + 1
            if length == 1 : 
                length = 0 
            max_length = max(max_length, length)
            i += 1
        
        return max_length

But this algorithm arose Time Limit Exceeded Error. So we have to make algorithm more faster. Using dictionary, we can find the number of element in input list. For example, in case of nums = [1, 2, 2, 2, 3, 3, 5, 7], we can get frequency table following : {1 : 1, 2 : 3, 3 : 2, 5 : 1, 7 : 1}. With this frequency table we can make above algorithm more faster. 

 

1. Start
2. Sort the input list. (nums)
3. Make frequency table using Counter method. (freqs)
4. Declare variable named max_length initialized with 0. (max_length)
5. Store keys of frequency table in list. (keys)
6. Repeat the steps through integers 0 to len(freqs) - 2.
   1. If keys[i+1] - keys[i] == 1, Update max_length as max(max_length, freqs[keys[i]] + freqs[keys[i+1]]).
7. Return the max_length.
8. End

 

3. Codes

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums = sorted(nums) 
        freqs = Counter(nums) 
        max_length = 0 
        keys = list(freqs.keys())
        n = len(keys)
   
        for i in range(n - 1) : 
            curr_key = keys[i]
            next_key = keys[i+1]
            if next_key - curr_key == 1 : 
                max_length = max(max_length, freqs[curr_key] + freqs[next_key])
        
        return max_length

 

4. Conclusion