Problem statement

A harmonious array is one where the difference between its maximum and minimum values is exactly 1.

Given an integer array nums, return the length of its longest harmonious subsequence. A subsequence keeps the relative order of the remaining elements but need not be contiguous. If no harmonious subsequence exists, return 0.

Example 1

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest is [3,2,2,2,3], using only the values 2 and 3.

Example 2

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

Example 3

Input: nums = [1,1,1,1]
Output: 0
Explanation: A single repeated value has max - min = 0, not 1.

Constraints

• 1 <= nums.length <= 40
• -1000 <= nums[i] <= 1000

Hints for Longest Harmonious Subsequence

1. Hint 1

   Order does not matter for a subsequence here — only how many copies of each value exist.

2. Hint 2

   A harmonious subsequence uses exactly two values, v and v + 1, and takes every copy of both.

3. Hint 3

   So count occurrences, then maximise count[v] + count[v + 1] over the values where both are present.

How to solve Longest Harmonious Subsequence

A harmonious subsequence uses exactly two values v and v + 1 and can take every copy of both, so the answer is the largest count[v] + count[v + 1] where both are present.

Approach

1. Count occurrences of every value.
2. For each v with v + 1 also present, compute count[v] + count[v + 1].
3. Return the maximum, or 0 if no such pair exists.

Why it works

Order never restricts a subsequence, so only multiplicities matter; requiring both values present enforces that max − min is exactly 1 rather than 0.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Counting a lone value (no v + 1) as harmonious is the classic wrong answer — a constant array returns 0.

Reference solution

Python

def findLHS(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    best = 0
    for v, c in count.items():
        if v + 1 in count:
            best = max(best, c + count[v + 1])
    return best

Java

public static int findLHS(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    int best = 0;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        Integer higher = count.get(e.getKey() + 1);
        if (higher != null) best = Math.max(best, e.getValue() + higher);
    }
    return best;
}

C++

int findLHS(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    int best = 0;
    for (auto& kv : count) {
        auto it = count.find(kv.first + 1);
        if (it != count.end()) best = max(best, kv.second + it->second);
    }
    return best;
}

JavaScript

var findLHS = function(nums) {
    const count = new Map();
    for (let i = 0; i < nums.length; i++) {
        count.set(nums[i], (count.get(nums[i]) || 0) + 1);
    }
    let best = 0;
    count.forEach(function(c, v) {
        const higher = count.get(v + 1);
        if (higher !== undefined && c + higher > best) best = c + higher;
    });
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy