Longest Harmonious Subsequence
EasyPrompt
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.
Example 1:
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation:
The longest harmonious subsequence is [3,2,2,2,3].
Example 2:
Input: nums = [1,2,3,4]
Output: 2
Explanation:
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
Explanation:
No harmonic subsequence exists.
Constraints:
1 <= nums.length <= 2 * 104-109 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each unique number in the array. For each number x, it checks if x+1 also exists. If it does, it then re-iterates through the entire original array to count the occurrences of x and x+1 to find the length of the harmonious subsequence they form. This process is repeated for every unique number, and the maximum length found is the result.
Algorithm
- Create a
Setof unique numbers from the input arraynumsto avoid redundant checks. - Initialize a variable
maxLengthto 0. - Iterate through each unique number
numin the set. - For each
num, check ifnum + 1also exists in the set. - If it does, this pair can form a harmonious subsequence. We then need to find its length.
- To find the length, iterate through the original
numsarray and count all elements that are equal tonumornum + 1. - Update
maxLengthwith the maximum length found so far. - After checking all unique numbers, return
maxLength.
Walkthrough
The brute-force method systematically checks every possible base number for a harmonious subsequence. First, we identify all unique numbers present in the input array nums by storing them in a HashSet. Then, for each unique number currentNum, we verify if its counterpart, currentNum + 1, is also present in the set. If both exist, they form a potential harmonious subsequence. To calculate its length, we perform a full scan of the original nums array, counting every occurrence of currentNum and currentNum + 1. This sum gives the length of the subsequence formed by this pair. We maintain a variable, maxLength, to keep track of the largest length found across all such pairs. While straightforward, this method is computationally expensive because of the repeated scans of the input array.
class Solution { public int findLHS(int[] nums) { int maxLength = 0; java.util.Set<Integer> uniqueNums = new java.util.HashSet<>(); for (int num : nums) { uniqueNums.add(num); } for (int num : uniqueNums) { if (uniqueNums.contains(num + 1)) { int currentLength = 0; for (int val : nums) { if (val == num || val == num + 1) { currentLength++; } } maxLength = Math.max(maxLength, currentLength); } } return maxLength; }}Complexity
Time
O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst-case scenario where all elements are unique, U = N, leading to a time complexity of O(N^2).
Space
O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).
Trade-offs
Pros
Simple to understand and implement.
Does not require complex data structures other than a set.
Cons
Highly inefficient due to nested iteration. The time complexity is quadratic in the worst case.
Redundant counting work. For a pair
(x, x+1), the counts are recalculated by iterating over the entire array.
This approach improves upon the brute-force method by first sorting the array. Once the array is sorted, all identical elements are grouped together, and potential harmonious pairs (x and x+1) are located near each other. We can then use a sliding window (or two-pointer) technique to efficiently find the longest subarray where the difference between the maximum and minimum element is exactly 1. This avoids the repeated scanning of the entire array.
Algorithm
- First, sort the input array
numsin non-decreasing order. - Initialize two pointers,
left = 0, and a variablemaxLength = 0. - Iterate through the array with a
rightpointer from0tonums.length - 1. - Inside the loop, advance the
leftpointer while the conditionnums[right] - nums[left] > 1is true. This shrinks the window from the left to ensure the difference between the max and min in the window is at most 1. - After adjusting
left, check ifnums[right] - nums[left] == 1. If it is, the current window[left, right]represents a harmonious subsequence. - Calculate its length as
right - left + 1and updatemaxLength = max(maxLength, right - left + 1). - After the loop finishes, return
maxLength.
Walkthrough
By sorting the array nums, we can efficiently find harmonious subsequences. After sorting, we can use a sliding window approach with two pointers, left and right. The right pointer expands the window by moving from left to right through the array. For each position of right, we check the difference nums[right] - nums[left]. If this difference is greater than 1, it means the window is too wide to be harmonious, so we shrink it by incrementing the left pointer. If the difference is exactly 1, we have found a valid harmonious subsequence. Its length is right - left + 1, and we update our maxLength if this is the longest one we've seen. If the difference is 0, all elements in the window are the same, which is not a harmonious subsequence, but we continue expanding the window as it might become part of one.
import java.util.Arrays; class Solution { public int findLHS(int[] nums) { Arrays.sort(nums); int maxLength = 0; int left = 0; for (int right = 0; right < nums.length; right++) { while (nums[right] - nums[left] > 1) { left++; } if (nums[right] - nums[left] == 1) { maxLength = Math.max(maxLength, right - left + 1); } } return maxLength; }}Complexity
Time
O(N log N), which is dominated by the initial sorting step. The subsequent two-pointer scan of the array takes O(N) time.
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm used. For instance, `Arrays.sort` in Java for primitives uses a variant of quicksort which has an average space complexity of O(log N) for the recursion stack.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
The sliding window logic is efficient, scanning the array only once after sorting.
Cons
The sorting step has a time complexity of O(N log N), which is not as efficient as the linear time solution.
The sorting modifies the original array's order, which might not be desirable in some contexts (though a copy can be made).
This is the most optimal approach. It uses a hash map to efficiently count the frequencies of all numbers in the input array in a single pass. After building this frequency map, it iterates through the unique numbers (the map's keys). For each number x, it checks if x+1 also exists in the map. If it does, the length of the harmonious subsequence is simply the sum of their frequencies, count(x) + count(x+1). The maximum of these sums is the answer.
Algorithm
- Create a
HashMapto store the frequency of each number. - Iterate through the input array
numsonce. For each number, update its count in the hash map. - Initialize a variable
maxLengthto 0. - Iterate through the keys (the unique numbers) of the hash map.
- For each key
num, check if the map also contains the keynum + 1. - If
num + 1exists in the map, it means we have a pair that forms a harmonious subsequence. - The length of this subsequence is the sum of the frequencies:
map.get(num) + map.get(num + 1). - Update
maxLengthwith the maximum sum found. - After iterating through all keys, return
maxLength.
Walkthrough
The core idea is that a harmonious subsequence is composed of only two distinct numbers, x and x+1. Therefore, its length is the total number of times x and x+1 appear in the original array. A hash map is the perfect data structure to solve this efficiently.
First, we iterate through the nums array and populate a hash map, where each key is a number from the array and its corresponding value is its frequency. This takes linear time.
Next, we iterate through the keys of the newly created frequency map. For each key num, we check if num + 1 also exists as a key in the map. If it does, we have found a valid pair for a harmonious subsequence. We calculate the length by summing their frequencies: freqMap.get(num) + freqMap.get(num + 1). We compare this length with our current maxLength and update it if the new length is greater. This second pass over the unique keys ensures we find the maximum possible length.
import java.util.HashMap;import java.util.Map; class Solution { public int findLHS(int[] nums) { Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } int maxLength = 0; for (int key : freqMap.keySet()) { if (freqMap.containsKey(key + 1)) { maxLength = Math.max(maxLength, freqMap.get(key) + freqMap.get(key + 1)); } } return maxLength; }}Complexity
Time
O(N). The first pass to build the frequency map takes O(N). The second pass iterates through the unique keys of the map, which is O(U) where U <= N. Thus, the overall time complexity is O(N).
Space
O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).
Trade-offs
Pros
Optimal time complexity of O(N).
Conceptually clean, directly addressing the problem by counting frequencies.
Only requires two passes over the data (one on the array, one on the unique keys).
Cons
Requires extra space to store the frequency map, which can be O(N) in the worst case where all elements are unique.
Solutions
Solution
class Solution {public int findLHS(int[] nums) { Map<Integer, Integer> counter = new HashMap<>(); for (int num : nums) { counter.put(num, counter.getOrDefault(num, 0) + 1); } int ans = 0; for (int num : nums) { if (counter.containsKey(num + 1)) { ans = Math.max(ans, counter.get(num) + counter.get(num + 1)); } } return ans; }}class Solution {public: int findLHS(vector<int> &nums) { unordered_map<int, int> counter; for (int num : nums) { ++counter[num]; } int ans = 0; for (int num : nums) { if (counter.count(num + 1)) { ans = max(ans, counter[num] + counter[num + 1]); } } return ans; }};class Solution: def findLHS(self, nums: List[int]) -> int: counter = Counter(nums) ans = 0 for num in nums: if num + 1 in counter: ans = max(ans, counter[num] + counter[num + 1]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.