594. Longest Harmonious Subsequence¶
Difficulty: Easy
LeetCode Problem View on GitHub
594. Longest Harmonious Subsequence
Easy
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
Solution¶
class Solution {
public int findLHS(int[] nums) {
int n = nums.length;
HashMap<Integer, TreeSet<Integer>> map = new HashMap<>();
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
if (!map.containsKey(nums[i])) map.put(nums[i], new TreeSet<>());
map.get(nums[i]).add(i);
}
int maxi = 0;
for (int i = 0; i < n; i++) {
TreeSet<Integer> current = map.get(nums[i] + 1);
if (current != null && current.size() > 0) {
maxi = Math.max(maxi, current.last() - i + 1);
}
}
return maxi;
}
}
Complexity Analysis¶
- Time Complexity:
O(?) - Space Complexity:
O(?)
Approach¶
Detailed explanation of the approach will be added here