Longest Harmonious Subsequence

(#594), Easy

Category: Array, Hash Table, Sliding Window, Sorting, 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

Explanation: The subsequence [2, 2, 2, 3, 3] is the longest harmonious subsequence.

Input: nums = [1, 2, 3, 4]

Output: 2

Explanation: Both [1, 2] and [2, 3] are valid, so the max is 2.

Input: nums = [1, 1, 1, 1]

Output: 0

Explanation: No other number to pair with 1, so output is 0.

Approach

Sliding Window (Brute Force)

Sort the array in ascending order.
Initialize two pointers: `start = 0` and `end = 0`.
Iterate through the array with `end` pointer.
While the difference between `nums[end]` and `nums[start]` is greater than 1, move `start` forward.
If the difference is exactly 1, calculate the window length as `end - start + 1` and update the maximum length found so far.
Return the maximum length after the loop ends.

var findLHS = function(nums) {
  nums.sort((a, b) => a - b);
  let start = 0, maxLen = 0;
  for (let end = 0; end < nums.length; end++) {
    while (nums[end] - nums[start] > 1) {
      start++;
    }
    if (nums[end] - nums[start] === 1) {
      maxLen = Math.max(maxLen, end - start + 1);
    }
  }
  return maxLen;
};

Optimized (Using Hash Map)

Create a HashMap to count the frequency of each element in the array.
Loop through each key in the HashMap.
For each key, check if `key + 1` exists in the HashMap.
If yes, add the counts of `key` and `key + 1`, and update the maximum length.
Return the maximum length found.

var findLHS = function(nums) {
  const map = new Map();
  for (let num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
  }
  let maxLen = 0;
  for (let [num, count] of map.entries()) {
    if (map.has(num + 1)) {
      maxLen = Math.max(maxLen, count + map.get(num + 1));
    }
  }
  return maxLen;
};

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.