We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Harmonious Subsequence

Number: 594

Difficulty: Easy

Paid? No

Companies: LiveRamp

Problem Description

Given an integer array, a harmonious array is defined as one in which the difference between its maximum and minimum values is exactly 1. The task is to find the length of the longest harmonious subsequence among all its possible subsequences.

Key Insights

  • Use a frequency table (hash map) to count the occurrences of each number.
  • For each unique number, check if its complement (number + 1) exists in the frequency table.
  • The potential harmonious subsequence length for a number is the sum of the count of that number and the count of (number + 1).
  • Track the maximum length obtained from the above sum; return 0 if no harmonious subsequence exists.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array, because we iterate through the array to build the frequency table and then iterate through the keys of the table. Space Complexity: O(n) in the worst case when all elements are unique, as we need to store counts for each element.

Solution

We solve the problem by first counting the frequency of each number in the array using a hash table. Then, iterate over each unique number and check if (number + 1) is present in the map. If found, add the two counts, and update the result if this sum is greater than the current record. This approach avoids unnecessary checks and leverages constant time access of hash tables.

Code Solutions

# Python solution
def findLHS(nums):
    # Create a dictionary to store frequency counts of numbers
    frequency = {}
    for num in nums:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
    
    # Initialize the result for maximum length found
    longest = 0
    
    # For each number, check if (number + 1) exists in the dictionary
    for num in frequency:
        if num + 1 in frequency:
            # Calculate the length of harmonious subsequence for this pair
            current_length = frequency[num] + frequency[num + 1]
            longest = max(longest, current_length)
    
    return longest

# Example usage:
print(findLHS([1,3,2,2,5,2,3,7]))  # Output should be 5
← Back to All Questions