Code Logo

Longest Harmonious Subsequence

Published at24 Jul 2026
Created by
Medium 1 views
Like0

A harmonious array is one where the difference between the maximum and minimum value is exactly 1. Given an integer array nums, return the length of its longest harmonious subsequence among all possible subsequences. A subsequence is a sequence derived by deleting some or no elements without changing the order of the remaining elements.

A brute force approach would generate all 2ⁿ subsequences, which is infeasible. The key insight is that the order of elements does not matter for determining whether a subsequence can be harmonious — we just need to count frequencies. If we have numbers x and x+1 in the array, we can form a harmonious subsequence by taking all occurrences of x and all occurrences of x+1.

This becomes a simple hash map frequency problem: count how many times each number appears. Then for each unique number n, check if n + 1 exists in the map. If so, the candidate length is freq[n] + freq[n + 1]. Track the maximum candidate across all numbers. This runs in O(n) time with O(n) space.

Edge cases include a single element (return 0, since min and max are the same), an array with no adjacent values (return 0), and an array with all same values (return 0 since max - min = 0, not 1).

Example Input & Output

Example 1
Input
[1,3,5,7]
Output
0
Explanation

No adjacent numbers exist.

Example 2
Input
[1,1,1,1]
Output
0
Explanation

All same, max-min=0 not 1.

Example 3
Input
[1,2,3,4]
Output
2
Explanation

Any adjacent pair gives length 2.

Example 4
Input
[1,3,2,2,5,2,3,7]
Output
5
Explanation

Subsequence [3,2,2,2,3] has max-min=1.

Example 5
Input
[1,1,2,2,3,3]
Output
4
Explanation

Best is [1,1,2,2] or [2,2,3,3].

Algorithm Flow

Recommendation Algorithm Flow for Longest Harmonious Subsequence

Solution Approach

Find the longest subsequence where the maximum and minimum values differ by exactly 1. Count the frequency of each number using a hash map. For each number, check if number + 1 also exists. The length of a harmonious subsequence using both numbers is freq[num] + freq[num + 1]. Track the maximum such sum.

function findLHS(nums) {
  var freq = {}, maxLen = 0;
  for (var i = 0; i < nums.length; i++) freq[nums[i]] = (freq[nums[i]] || 0) + 1;
  for (var num in freq) {
    if (freq[parseInt(num) + 1]) {
      var len = freq[num] + freq[parseInt(num) + 1];
      if (len > maxLen) maxLen = len;
    }
  }
  return maxLen;
}

Only adjacent values (differing by 1) can form a harmonious subsequence. The sum of their frequencies gives the longest possible subsequence containing both values.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Map<Integer,Integer> freq = new HashMap<>();
        for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);
        int best = 0;
        for (int n : freq.keySet()) {
            if (freq.containsKey(n + 1)) {
                best = Math.max(best, freq.get(n) + freq.get(n + 1));
            }
        }
        return best;
    }
}