Code Logo

Longest Harmonious Subsequence

Published at24 Jul 2026
Created by
Medium 0 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
Recommendation Algorithm Flow for Longest Harmonious Subsequence

Solution Approach

Build a frequency hash map. For each key x, if x+1 exists, sum their frequencies and track the maximum.

function solution(nums) {
  var freq = {};
  for (var i = 0; i < nums.length; i++) {
    freq[nums[i]] = (freq[nums[i]] || 0) + 1;
  }
  var best = 0;
  for (var k in freq) {
    var x = ~~k;
    if (freq[x + 1]) {
      var len = freq[x] + freq[x + 1];
      if (len > best) best = len;
    }
  }
  return best;
}

Time O(n), Space 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;
    }
}