problemeasyalgorithmsleetcode-594leetcode 594leetcode594

Longest Harmonious Subsequence

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

Examples

Example 1


Input: nums = [1,3,2,2,5,2,3,7]

Output: 5

Explanation:

The longest harmonious subsequence is `[3,2,2,2,3]`.

Example 2


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

Output: 2

Explanation:

The longest harmonious subsequences are `[1,2]`, `[2,3]`, and `[3,4]`, all of
which have a length of 2.

Example 3


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

Output: 0

Explanation:

No harmonic subsequence exists.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10^9 <= nums[i] <= 10^9

Solution

Method 1 – Hash Map Counting (1)

Intuition

A harmonious subsequence has elements whose max and min differ by exactly 1. By counting the frequency of each number, we can efficiently check for pairs of numbers that differ by 1 and sum their counts for the answer.

Approach

  1. Count the frequency of each number in the array using a hash map.
  2. For each unique number, if the number+1 exists in the map, sum their counts and update the answer if it's larger.
  3. Return the maximum sum found.

Code

C++
class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) cnt[x]++;
        int ans = 0;
        for (auto& [k, v] : cnt) {
            if (cnt.count(k+1)) ans = max(ans, v + cnt[k+1]);
        }
        return ans;
    }
};
Go
func findLHS(nums []int) int {
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }
    ans := 0
    for k, v := range cnt {
        if c, ok := cnt[k+1]; ok {
            if v+c > ans {
                ans = v + c
            }
        }
    }
    return ans
}
Java
class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        int ans = 0;
        for (int k : cnt.keySet()) {
            if (cnt.containsKey(k+1)) ans = Math.max(ans, cnt.get(k) + cnt.get(k+1));
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun findLHS(nums: IntArray): Int {
        val cnt = mutableMapOf<Int, Int>()
        for (x in nums) cnt[x] = cnt.getOrDefault(x, 0) + 1
        var ans = 0
        for ((k, v) in cnt) {
            if (cnt.containsKey(k+1)) ans = maxOf(ans, v + cnt[k+1]!!)
        }
        return ans
    }
}
Python
class Solution:
    def findLHS(self, nums: list[int]) -> int:
        from collections import Counter
        cnt = Counter(nums)
        ans = 0
        for k in cnt:
            if k+1 in cnt:
                ans = max(ans, cnt[k] + cnt[k+1])
        return ans
Rust
impl Solution {
    pub fn find_lhs(nums: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        for &x in &nums {
            *cnt.entry(x).or_insert(0) += 1;
        }
        let mut ans = 0;
        for (&k, &v) in &cnt {
            if let Some(&c) = cnt.get(&(k+1)) {
                ans = ans.max(v + c);
            }
        }
        ans
    }
}
TypeScript
class Solution {
    findLHS(nums: number[]): number {
        const cnt = new Map<number, number>();
        for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
        let ans = 0;
        for (const [k, v] of cnt.entries()) {
            if (cnt.has(k+1)) ans = Math.max(ans, v + cnt.get(k+1)!);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We count and check each number once.
  • 🧺 Space complexity: O(m), where m is the number of unique numbers in nums, for the hash map.

Comments