Leetcode – Longest Harmonious Subsequence Solution in Python

Spread the love

One of the more intriguing array-based problems on LeetCode is the Longest Harmonious Subsequence (#594). This problem tests your understanding of hash maps and array manipulation. In this article, we will dissect the problem, understand its constraints, and learn how to solve it efficiently in Python.

Problem Statement

The problem statement is as follows:

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.

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.

Example:

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

Approaches to Solve the Problem

1. Using Hash Maps

To solve this problem efficiently, we can use a hash map to store the frequency of each number in the array. Once we have the frequency of each number, we can iterate through the keys of the hash map and for each key, we check if key + 1 exists in the map. The length of the harmonious subsequence ending at key would be the sum of the frequency of key and the frequency of key + 1.

def findLHS(nums):
    # Count the frequency of each number
    frequency_map = {}
    for num in nums:
        frequency_map[num] = frequency_map.get(num, 0) + 1
    
    # Find the longest harmonious subsequence
    max_length = 0
    for key in frequency_map:
        if key + 1 in frequency_map:
            max_length = max(max_length, frequency_map[key] + frequency_map[key + 1])
            
    return max_length

Explanation:

  1. Iterate through the numbers in nums, and for each number, increase its count in frequency_map.
  2. For each unique number, check if the number + 1 is also in the array. If so, calculate the sum of the counts of the number and the number + 1, and keep track of the maximum sum encountered.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of elements in the array. The space complexity is also O(n) as we need to store the frequency of each number.

2. Sorting the Array (Less Efficient)

Another approach to solving this problem is to first sort the array and then find the longest harmonious subsequence. This approach is less efficient compared to the hash map approach but is a good alternative when hash map usage is restricted or not viable for some reason.

def findLHS(nums):
    # Sort the array
    nums.sort()
    
    # Find the longest harmonious subsequence
    prev_count = 1
    max_length = 0
    current_length = 0
    for i in range(1, len(nums)):
        if nums[i] - nums[i-1] == 1:
            current_length = prev_count + 1
        elif nums[i] == nums[i-1]:
            prev_count += 1
            continue
        else:
            prev_count = 1
            current_length = 0
        
        max_length = max(max_length, current_length)
        current_length += 1
        
    return max_length

Explanation:

  1. First, sort the input array.
  2. Iterate through the sorted array. For each number, if the difference between the current and previous numbers is 1, then it is part of a harmonious subsequence.
  3. Keep track of the maximum length encountered.

Time Complexity:

The time complexity of this approach is O(n log n) due to the sorting step, and the space complexity is O(1).

Concluding Thoughts

The Longest Harmonious Subsequence problem is an interesting array manipulation problem that combines elements of hashing and sorting. The hash map approach is generally more efficient and should be preferred for large datasets. However, the sorting approach provides a different perspective on the problem.

Leave a Reply