This problem requires identifying the longest harmonious subsequence where the maximum and minimum differ by exactly one. By scanning the array and tracking element counts in a hash table, you can efficiently determine valid subsequences. The key insight is pairing each number with its consecutive neighbor and summing their frequencies to find the longest valid sequence.
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.
How GhostInterview Helps
- Automatically identifies the longest harmonious subsequence length using hash map frequency counting.
- Highlights potential failure modes like missing consecutive neighbors or identical elements arrays.
- Provides step-by-step logic for array scanning plus hash lookup to match interview-level expectations.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Longest Harmonious Subsequence instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Longest Harmonious Subsequence from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Task Scheduler is solved by counting task frequencies and computing how cooldown gaps force idle slots around the most frequent task.
Open problem page#632 Smallest Range Covering Elements from K ListsFind the minimal range covering at least one number from each of k sorted lists using array scanning and hash lookup efficiently.
Open problem page#692 Top K Frequent WordsSolve Top K Frequent Words by counting each word, then ordering ties alphabetically so frequency wins before lexicographic comparison.
Open problem page