#594

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Harmonious Subsequence

Find the length of the longest harmonious subsequence in an integer array using array scanning and hash-based frequency counting techniques.

array hash table sliding window sorting counting

Problem Statement

A harmonious array is defined as an array where the difference between the largest and smallest values is exactly 1. Given an integer array nums, determine the length of the longest subsequence that satisfies this property. Each subsequence is formed by selecting elements from the array without changing their order but does not need to be contiguous.

For example, given nums = [1,3,2,2,5,2,3,7], the longest harmonious subsequence is [3,2,2,2,3], which has a length of 5. Return 0 if no harmonious subsequence exists. Consider arrays of size up to 2 * 10^4 with elements ranging from -10^9 to 10^9.

Examples

Example 1

Input: nums = [1,3,2,2,5,2,3,7]

Output: 5

The longest harmonious subsequence is [3,2,2,2,3] .

Example 2

Input: nums = [1,2,3,4]

Output: 2

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

Example 3

Input: nums = [1,1,1,1]

Output: 0

No harmonic subsequence exists.

Constraints

1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109

Solution Approach

Use a Hash Map for Frequency Counting

Scan the array once and record the frequency of each number in a hash map. For every key in the hash map, check if key + 1 exists. If it does, calculate the sum of counts for key and key + 1 to consider as a candidate harmonious subsequence. Keep track of the maximum sum encountered.

Iterate Through Unique Numbers Only

After building the frequency map, iterate only through the unique numbers instead of the entire array. This avoids redundant computations and ensures that each potential harmonious pair is considered exactly once. Update the maximum length whenever a valid pair is found.

Return Zero if No Harmonious Pair Exists

If no key has a consecutive neighbor in the map, the array contains no harmonious subsequence. Explicitly check this case and return 0. This handles edge cases like arrays of identical elements, e.g., [1,1,1,1].

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) to build the frequency map and O(k) to iterate through unique numbers, where k is the number of distinct elements. Space complexity is O(k) for the hash map. Sorting-based approaches would increase time to O(n log n), so hash-based counting is optimal for larger arrays.

What Interviewers Usually Probe

Do you know a way to avoid checking every possible subsequence?
Can you leverage a hash table to count occurrences and simplify the comparison?
How would you handle arrays where all elements are identical?

Common Pitfalls or Variants

Common pitfalls

Forgetting that subsequences do not need to be contiguous, leading to incorrect slicing logic.
Summing frequencies incorrectly or checking non-consecutive numbers, which produces invalid subsequences.
Not returning 0 for arrays where no harmonious pair exists, e.g., all elements identical.

Follow-up variants

Return the actual longest harmonious subsequence array instead of just its length.
Modify the problem to find subsequences where the max and min differ by exactly k instead of 1.
Determine the number of distinct harmonious subsequences of maximum length.

FAQ

What is the main pattern used to solve Longest Harmonious Subsequence?

The primary pattern is array scanning combined with hash table frequency counting to identify valid consecutive pairs efficiently.

Can this problem be solved without a hash table?

Yes, sorting the array and using a sliding window approach can also work, but hash tables provide O(n) efficiency for large inputs.

What should be returned if all array elements are identical?

Return 0 since no two distinct numbers exist to form a harmonious subsequence.

How do we handle negative numbers in the array?

Negative numbers are treated the same way; count their frequencies and check if consecutive numbers exist, just as with positive numbers.

Is the subsequence required to be contiguous?

No, subsequences can skip elements, but the maximum and minimum difference must be exactly 1 within the selected elements.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{cnt}$ to record the occurrence count of each element in the array $\textit{nums}$. Then, we iterate through each key-value pair $(x, c)$ in the hash table. If the key $x + 1$ exists in the hash table, then the sum of occurrences of elements $x$ and $x + 1$, $c + \textit{cnt}[x + 1]$, forms a harmonious subsequence. We just need to find the maximum length among all harmonious subsequences.

1

2

3

4

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)

Continue Practicing

#621 task scheduler #632 smallest range covering elements from k lists #692 top k frequent words