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] <= 109This approach leverages a map (or dictionary in Python) to count the frequency of each number in the array. Once we know the count of each number, we can iterate through the keys and check for pairs of consecutive numbers (n and n+1). The length of a harmonious subsequence that can be formed is the sum of the counts of these consecutive numbers.
The C solution uses an array to act as a hashmap to count occurrences of numbers. A large integer array of size 2 billion is declared to accommodate the range of input, offset by 1 billion to handle negative values by shifting index.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(n)
An alternative approach would be to sort the numbers. After sorting, we can use a two-pointer technique to find the longest subsequence where the difference between the smallest and largest value is exactly one. This method may be less efficient due to the sorting step but provides a straightforward solution.
The C implementation uses the qsort function to first sort the array, and then applies a two-pointer technique to find the longest subsequence with the desired difference of one.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) if counting sort or constant space partition approach is used.
| Approach | Complexity |
|---|---|
| HashMap for Counting Elements | Time Complexity: O(n), Space Complexity: O(n) |
| Sorting Solution | Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) if counting sort or constant space partition approach is used. |
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 views views
Watch 9 more video solutions →Practice Longest Harmonious Subsequence with our built-in code editor and test cases.
Practice on FleetCode