594. Longest Harmonious Subsequence
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 51.3%
Problem Breakdown
The problem asks us to find the length of the longest harmonious subsequence in an integer array nums. A harmonious subsequence is defined as a subsequence where the difference between its maximum value and minimum value is exactly 1. The input is an array of integers, and the output should be an integer representing the length of the longest such subsequence.
Inputs:
- An integer array
numswith length ranging from 1 to 20,000. - Each element in
numscan range from -10^9 to 10^9.
Outputs:
- An integer representing the length of the longest harmonious subsequence.
Implicit Constraints/Edge Cases:
- If there are no such subsequences (e.g., all elements are the same), the output should be 0.
- The array can contain negative numbers, which need to be handled correctly when checking for harmonious pairs.
- The array can have duplicate elements, and these duplicates should be considered in forming the subsequence.
Intuition
A brute-force approach would involve generating all possible subsequences of nums and checking if each one is harmonious. This approach is computationally expensive with a time complexity of O(2^n), which is not feasible given the constraints.
The key insight to improve this is to use a hash table (dictionary) to count the occurrences of each number in nums. By leveraging these counts, we can efficiently determine the length of harmonious subsequences by checking pairs of consecutive numbers (i.e., num and num + 1) in the sorted keys of the dictionary.
Approach
- Count Frequencies: Use a hash table to count the occurrences of each number in
nums. - Identify Harmonious Pairs: Iterate through the keys of the hash table, checking for pairs of consecutive numbers.
- Calculate Lengths: For each harmonious pair
(num, num + 1), calculate the length of the subsequence as the sum of their counts. - Track Maximum Length: Keep track of the maximum length found during the iteration.
Complexity Analysis
- Time Complexity: O(n), where n is the number of elements in
nums. This is because we iterate through the array once to count frequencies and then iterate through the unique elements (which are at most n). - Space Complexity: O(n) for storing the frequency counts in the hash table.
Solution
def findLHS(nums):
from collections import Counter
# Step 1: Count the occurrences of each number
count = Counter(nums)
max_length = 0
# Step 2: Iterate through the unique numbers
for num in count:
# Check if there is a consecutive number (num + 1) that forms a harmonious pair
if num + 1 in count:
# Calculate the length of the harmonious subsequence
current_length = count[num] + count[num + 1]
# Update max_length if the current_length is greater
max_length = max(max_length, current_length)
return max_length
# Example usage:
print(findLHS([1,3,2,2,5,2,3,7])) # Output: 5
print(findLHS([1,2,3,4])) # Output: 2
print(findLHS([1,1,1,1])) # Output: 0
Edge Cases Handled
- All elements are the same: The code correctly returns 0 since there are no harmonious pairs.
- Negative numbers: The code handles negative numbers correctly by checking for consecutive pairs in the sorted keys of the dictionary.
- Empty input array: Although not explicitly mentioned, if
numsis empty, the function will return 0 as expected.