Longest Harmonious Subsequence

easy hash map counter

Problem

Return the longest subsequence whose max value − min value is exactly 1.

Inputnums = [1,3,2,2,5,2,3,7]

Output5

Values 2 and 3 — count 3 + 2 = 5.

input

def find_lhs(nums):
    from collections import Counter
    c = Counter(nums)
    return max((c[x] + c[x+1] for x in c if x+1 in c), default=0)

function findLHS(nums) {
  const c = new Map();
  nums.forEach(x => c.set(x, (c.get(x)||0)+1));
  let best = 0;
  for (const [x, v] of c) if (c.has(x+1)) best = Math.max(best, v + c.get(x+1));
  return best;
}

int findLHS(int[] nums) {
    Map c = new HashMap<>();
    for (int x : nums) c.merge(x, 1, Integer::sum);
    int best = 0;
    for (var e : c.entrySet()) if (c.containsKey(e.getKey()+1)) best = Math.max(best, e.getValue() + c.get(e.getKey()+1));
    return best;
}

int findLHS(vector& nums) {
    unordered_map c;
    for (int x : nums) c[x]++;
    int best = 0;
    for (auto& [k, v] : c) if (c.count(k+1)) best = max(best, v + c[k+1]);
    return best;
}

Explanation

A harmonious subsequence has a max and min that differ by exactly 1. That means it can only contain two adjacent values: some x and x + 1. To make it as long as possible, we just grab every copy of both.

So the length for a chosen x is simply count[x] + count[x+1] — but only when x + 1 actually exists in the array (otherwise there's no pair and it doesn't count).

We build a counter c of how often each value appears, then for every value x that has a neighbor x + 1 present, we compute c[x] + c[x+1] and keep the maximum.

Example: nums = [1,3,2,2,5,2,3,7]. Counts: 1:1, 2:3, 3:2, 5:1, 7:1. For x = 2 we get c[2] + c[3] = 3 + 2 = 5, which is the best, so the answer is 5.

If no value has its x + 1 partner present, no harmonious subsequence exists and the answer is 0.

Time: O(n) Space: O(n)