Longest Harmonious Subsequence(#594)
Category: Array, Hash Map, Sliding Window, Sorting, Frequency Count, Two Pointer
🧩 Problem Statement
We define a harmonious array as one where the difference between the maximum and minimum element is exactly 1. Given an array `nums`, return the length of the longest harmonious subsequence you can find. A subsequence can be formed by deleting some or no elements without changing the order of the remaining elements.
📚 Examples
Input: nums = [1, 3, 2, 2, 5, 2, 3, 7]
Output: 5
Input: nums = [1, 2, 3, 4]
Output: 2
Input: nums = [1, 1, 1, 1]
Output: 0
🧠 Approach
Approach 1:
Sliding Window (Brute Force)
• Sort the array.
• Use two pointers `start` and `end` to slide over the array.
• If the difference between nums[end] and nums[start] > 1, move `start` forward.
• If the difference is exactly 1, calculate the window length and update max.
Approach 2:
Optimized HashMap
• Build a frequency map of all numbers.
• For each number in the map, check if `num + 1` exists.
• If yes, add `map[num] + map[num + 1]` and update the result.
💻 Code
// 🔹 Approach 1: Brute Force (Using Sliding Window)
var findLHS = function(nums) {
nums.sort((a, b) => a - b); // Sort the array
let start = 0, maxLen = 0;
for (let end = 0; end < nums.length; end++) {
while (nums[end] - nums[start] > 1) {
start++; // Shrink window if diff > 1
}
if (nums[end] - nums[start] === 1) {
maxLen = Math.max(maxLen, end - start + 1); // Update max length
}
}
return maxLen;
};
console.log(findLHS([1, 3, 2, 2, 5, 2, 3, 7])); // Output: 5
console.log(findLHS([1, 2, 3, 4])); // Output: 2
// 🔹 Approach 2: Optimized (Using Hash Map)
var findLHS = function(nums) {
const map = new Map();
for (let num of nums) {
map.set(num, (map.get(num) || 0) + 1); // Count frequency
}
let maxLen = 0;
for (let [num, count] of map.entries()) {
if (map.has(num + 1)) {
maxLen = Math.max(maxLen, count + map.get(num + 1)); // Combine with neighbor
}
}
return maxLen;
};
console.log(findLHS([1, 3, 2, 2, 5, 2, 3, 7])); // Output: 5
console.log(findLHS([1, 2, 3, 4])); // Output: 2📈 Complexity
Time: Brute Force: O(n log n) due to sorting. Optimized: O(n) using hash map.
Space: Brute Force: O(1) or O(n) (depends on sort). Optimized: O(n) for the frequency map.