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

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


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

Output: 0

Explanation:

No harmonic subsequence exists.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -109 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
    }
}
1
2
3
4
5
6
7
8
9

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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.