Taro Logo

Longest Harmonious Subsequence

Easy
Apple logo
Apple
Topics:
ArraysDynamic Programming

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 array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

For example:

  1. nums = [1,3,2,2,5,2,3,7] The longest harmonious subsequence is [3,2,2,2,3]. The function should return 5.

  2. nums = [1,2,3,4] The longest harmonious subsequences are [1,2], [2,3], and [3,4], all of which have a length of 2. The function should return 2.

  3. nums = [1,1,1,1] No harmonic subsequence exists. The function should return 0.

Could you provide a function that efficiently calculates the length of the longest harmonious subsequence, considering potential edge cases and optimizing for time and space complexity?

Solution


Brute Force Solution

A brute force solution would involve generating all possible subsequences of the input array and then checking each subsequence to see if it is harmonious. For each subsequence, we would need to find the maximum and minimum values and check if their difference is exactly 1. If it is, we would update the length of the longest harmonious subsequence found so far.

def findLHS_brute_force(nums):
    max_len = 0
    for i in range(1 << len(nums)):
        subsequence = []
        for j in range(len(nums)):
            if (i >> j) & 1:
                subsequence.append(nums[j])
        
        if not subsequence:
            continue
        
        max_val = max(subsequence)
        min_val = min(subsequence)
        
        if max_val - min_val == 1:
            max_len = max(max_len, len(subsequence))
            
    return max_len

Time Complexity

The time complexity of this brute force solution is O(2n * n), where n is the length of the input array. This is because there are 2n possible subsequences, and for each subsequence, we need to iterate through its elements to find the maximum and minimum values, which takes O(n) time.

Space Complexity

The space complexity is O(n) in the worst case, due to storing the subsequence.

Optimal Solution

The optimal solution involves using a hash map (or dictionary) to store the frequency of each number in the input array. Then, we iterate through the hash map and check if the number + 1 exists in the hash map. If it does, we calculate the sum of the frequencies of the number and number + 1 and update the length of the longest harmonious subsequence found so far.

def findLHS(nums):
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    max_len = 0
    for num in freq_map:
        if num + 1 in freq_map:
            max_len = max(max_len, freq_map[num] + freq_map[num + 1])
            
    return max_len

Time Complexity

The time complexity of this optimal solution is O(n), where n is the length of the input array. This is because we iterate through the array once to build the hash map, and then we iterate through the hash map, which in the worst case can have n elements.

Space Complexity

The space complexity is O(n), where n is the number of distinct elements in the input array. This is because, in the worst-case scenario, all the elements in the array are distinct, and we need to store the frequency of each element in the hash map.

Edge Cases

  • If the input array is empty, the length of the longest harmonious subsequence is 0.
  • If the input array contains only one distinct number, the length of the longest harmonious subsequence is 0.
  • If no harmonious subsequence exists, the function should return 0.