A harmonious array is one where the difference between its maximum and minimum value is exactly 1. Given nums, return the length of the longest harmonious subsequence (elements don't need to be contiguous — but order and duplicates are fixed by the original array).

Engineering takeaway. "Subsequence, not subarray" means we only care about counts, not positions. Whenever a problem cares about how many times values appear rather than where, reach for a frequency map first — it converts a two-dimensional search into a handful of O(1) lookups.

Intuition

If the max and min of the subsequence differ by exactly 1, then the subsequence can only contain values v and v + 1 (for some v). Its length is simply:

count(v) + count(v + 1)

So the problem collapses to: for each value in the array, is there a neighbor v ± 1 present? If so, what's the biggest count(v) + count(v + 1) we can form?

Approach

  1. Count every value with a Map.
  2. For each distinct value num, check if num + 1 exists.
  3. Track the maximum freq[num] + freq[num + 1].

Checking only num + 1 (not num - 1) avoids double-counting each pair.

function findLHS(nums: number[]): number {
  const freq = new Map<number, number>();
  let answer = 0;
 
  for (const num of nums) {
    freq.set(num, (freq.get(num) ?? 0) + 1);
  }
 
  for (const [num, count] of freq) {
    const next = freq.get(num + 1);
    if (next !== undefined) {
      answer = Math.max(answer, count + next);
    }
  }
 
  return answer;
}

Complexity

  • Time: O(n) — one pass to count, one pass over distinct keys.
  • Space: O(n) — for the frequency map.

The lesson

"Subsequence" is a hint: order doesn't matter, so counts matter. The moment you translate a problem into frequencies, a hash map almost always wins. It's the same instinct behind caching — precompute the answer to the most expensive question (how many of value v exist?) and answer it in O(1).