Longest Harmonious Subsequence solution and explanation
Google
9 more videos on this problem
Longest Harmonious Subsequence | Live Coding with Explanation | Leetcode #594Algorithms Made Easy · 6:48 · 10K views
Longest Harmonious Subsequence | Test your IQ | Leetcode 594 | codestorywithMIKcodestorywithMIK · 22:35 · 8K views
Leetcode - Longest Harmonious Subsequence (Python)Timothy H Chang · 7:25 · 3K views
Longest Harmonious Subsequence | Leetcode 594Coding Decoded · 13:31 · 1K views
594. Longest Harmonious Subsequence | Leetcode Daily - PythonLeetcode Daily · 4:53 · 1K views
594. Longest Harmonious Subsequence | Two Pointers | Sliding Window | HashMap | LeetcodeRapid Syntax · 12:24 · 916 views
Leetcode 594. Longest Harmonious Subsequence | Leetcode 594 Explained in Python | HashMap LogicStatLearn Tech · 13:30 · 775 views
594. Longest Harmonious Subsequence (Leetcode Easy)Programming Live with Larry · 10:37 · 760 views
Leetcode #594. Longest Harmonious Subsequence - Python - HashmapHrant · 6:39 · 514 views
Longest Harmonious Subsequence | Leetcode 594 | HashMap | Sorting + Sliding WindowAbhinav Bansal · 8:56 · 206 views
The 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.
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 * 104-109 <= nums[i] <= 109
Approach overview
Problem Overview: Given an integer array nums, find the length of the longest harmonious subsequence. A subsequence is harmonious if the difference between its maximum and minimum values is exactly 1. Elements do not need to remain contiguous, but they must come from the original array.
Approach 1: HashMap for Counting Elements (O(n) time, O(n) space)
This approach counts the frequency of every number using a hash map. After building the frequency table, iterate through each unique value x and check whether x + 1 exists. If it does, the total length of a harmonious subsequence formed by those values is count[x] + count[x+1]. Track the maximum across all such pairs. The key insight: a harmonious subsequence only depends on the counts of two consecutive integers, not their positions. Hash lookups run in constant time, so the entire process completes in O(n) time. This method heavily relies on efficient counting with a hash table and works well for unsorted arrays.
Approach 2: Sorting + Sliding Window (O(n log n) time, O(1) extra space)
Another option sorts the array first. Once sorted, numbers with similar values appear next to each other. Use two pointers to maintain a window where the difference between the current maximum and minimum stays ≤ 1. Expand the right pointer while the condition holds. If the difference exceeds 1, move the left pointer forward. Whenever the difference equals exactly 1, update the maximum window length. Sorting costs O(n log n), while the two-pointer scan runs in O(n). This approach is intuitive if you are comfortable with sorting and sliding window patterns.
The sorted method works well when modifying the input array is acceptable and you prefer pointer-based reasoning. The hash map approach is typically faster in practice because it avoids sorting and directly uses element frequencies.
Recommended for interviews: The hash map counting approach is usually what interviewers expect. It demonstrates strong understanding of frequency counting and constant-time lookups. Mentioning the sorting approach shows you considered multiple strategies, but implementing the O(n) hash-based solution proves you can optimize beyond brute-force comparisons.
Approach 1: HashMap for Counting Elements
This approach leverages a map (or dictionary in Python) to count the frequency of each number in the array. Once we know the count of each number, we can iterate through the keys and check for pairs of consecutive numbers (n and n+1). The length of a harmonious subsequence that can be formed is the sum of the counts of these consecutive numbers.
from collections import Counter
def findLHS(nums):
count = Counter(nums)
max_length = 0
for num in count:
if num + 1 in count:
max_length = max(max_length, count[num] + count[num + 1])
return max_lengthimport java.util.HashMap;
public class Solution {
public int findLHS(int[] nums) {
HashMap<Integer, Integer> countMap = new HashMap<>();
for(int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
int maxLength = 0;
for(int key : countMap.keySet()) {
if(countMap.containsKey(key + 1)) {
maxLength = Math.max(maxLength, countMap.get(key) + countMap.get(key + 1));
}
}
return maxLength;
}
}#include <vector>
#include <unordered_map>
using namespace std;
int findLHS(vector<int>& nums) {
unordered_map<int, int> numCount;
for(auto num : nums) {
numCount[num]++;
}
int maxLength = 0;
for(auto& pair : numCount) {
if(numCount.find(pair.first + 1) != numCount.end()) {
maxLength = max(maxLength, pair.second + numCount[pair.first + 1]);
}
}
return maxLength;
}var findLHS = function(nums) {
let countMap = new Map();
for (let num of nums) {
countMap.set(num, (countMap.get(num) || 0) + 1);
}
let maxLength = 0;
for (let [key, value] of countMap.entries()) {
if (countMap.has(key + 1)) {
maxLength = Math.max(maxLength, value + countMap.get(key + 1));
}
}
return maxLength;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int findLHS(int* nums, int numsSize){
int map[2000000000] = {0}, offset = 1000000000;
int maxLength = 0;
for(int i = 0; i < numsSize; i++) {
map[nums[i] + offset]++;
}
for(int i = 0; i < 2000000000; i++) {
if(map[i] > 0 && map[i+1] > 0) {
int currentLength = map[i] + map[i+1];
if (currentLength > maxLength) {
maxLength = currentLength;
}
}
}
return maxLength;
}using System;
using System.Collections.Generic;
public class Solution {
public int FindLHS(int[] nums) {
Dictionary<int, int> countDictionary = new Dictionary<int, int>();
foreach (var num in nums) {
if (countDictionary.ContainsKey(num)) {
countDictionary[num]++;
} else {
countDictionary[num] = 1;
}
}
int maxLength = 0;
foreach (var key in countDictionary.Keys) {
if (countDictionary.ContainsKey(key + 1)) {
maxLength = Math.Max(maxLength, countDictionary[key] + countDictionary[key + 1]);
}
}
return maxLength;
}
}Using Python's Counter from the collections module, the frequency of each number is counted. We then iterate through the counted numbers to find pairs of consecutive numbers.
Time Complexity: O(n), Space Complexity: O(n)
Approach 2: Sorting Solution
An alternative approach would be to sort the numbers. After sorting, we can use a two-pointer technique to find the longest subsequence where the difference between the smallest and largest value is exactly one. This method may be less efficient due to the sorting step but provides a straightforward solution.
def findLHS(nums):
nums.sort()
left, maxLength = 0, 0
for right in range(1, len(nums)):
while nums[right] - nums[left] > 1:
left += 1
if nums[right] - nums[left] == 1:
maxLength = max(maxLength, right - left + 1)
return maxLengthimport java.util.Arrays;
public class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);
int left = 0, maxLength = 0;
for (int right = 1; right < nums.length; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}
if (nums[right] - nums[left] == 1) {
maxLength = Math.max(maxLength, right - left + 1);
}
}
return maxLength;
}
}#include <vector>
#include <algorithm>
using namespace std;
int findLHS(vector<int>& nums) {
sort(nums.begin(), nums.end());
int left = 0, maxLength = 0;
for (int right = 1; right < nums.size(); ++right) {
while (nums[right] - nums[left] > 1) {
++left;
}
if (nums[right] - nums[left] == 1) {
maxLength = max(maxLength, right - left + 1);
}
}
return maxLength;
}var findLHS = function(nums) {
nums.sort((a, b) => a - b);
let left = 0, maxLength = 0;
for (let right = 1; right < nums.length; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}
if (nums[right] - nums[left] == 1) {
maxLength = Math.max(maxLength, right - left + 1);
}
}
return maxLength;
};#include <stdio.h>
#include <stdlib.h>
int cmp (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int findLHS(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), cmp);
int left = 0, maxLength = 0;
for (int right = 1; right < numsSize; right++) {
while (nums[right] - nums[left] > 1) left++;
if (nums[right] - nums[left] == 1) {
maxLength = (right - left + 1) > maxLength ? (right - left + 1) : maxLength;
}
}
return maxLength;
}using System;
public class Solution {
public int FindLHS(int[] nums) {
Array.Sort(nums);
int left = 0, maxLength = 0;
for (int right = 1; right < nums.Length; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}
if (nums[right] - nums[left] == 1) {
maxLength = Math.Max(maxLength, right - left + 1);
}
}
return maxLength;
}
}The Python solution sorts the array, and then employs a two-pointer strategy to dynamically find and measure qualifying subsequences.
Time Complexity: O(n log n), Space Complexity: O(1)
Approach 3: Hash Table
We can use a hash table cnt to record the occurrence count of each element in the array nums. Then, we iterate through each key-value pair (x, c) in the hash table. If the key x + 1 exists in the hash table, then the sum of occurrences of elements x and x + 1, c + cnt[x + 1], forms a harmonious subsequence. We just need to find the maximum length among all harmonious subsequences.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
function findLHS(nums: number[]): number {
const cnt: Record<number, number> = {};
for (const x of nums) {
cnt[x] = (cnt[x] || 0) + 1;
}
let ans = 0;
for (const [x, c] of Object.entries(cnt)) {
const y = +x + 1;
if (cnt[y]) {
ans = Math.max(ans, c + cnt[y]);
}
}
return ans;
}func findLHS(nums []int) (ans int) {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
for x, c := range cnt {
if c1, ok := cnt[x+1]; ok {
ans = max(ans, c+c1)
}
}
return
}use std::collections::HashMap;
impl Solution {
pub fn find_lhs(nums: Vec<i32>) -> i32 {
let mut cnt = HashMap::new();
for &x in &nums {
*cnt.entry(x).or_insert(0) += 1;
}
let mut ans = 0;
for (&x, &c) in &cnt {
if let Some(&y) = cnt.get(&(x + 1)) {
ans = ans.max(c + y);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap for Counting Elements | Time Complexity: O(n), Space Complexity: O(n) |
| Sorting Solution | Time Complexity: O(n log n), Space Complexity: O(1) |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap for Counting Elements | O(n) | O(n) | Best general solution. Works efficiently for unsorted arrays using frequency counting. |
| Sorting + Sliding Window | O(n log n) | O(1) extra | Useful when sorting is acceptable and you prefer two-pointer window logic. |
Frequently asked questions
Is Longest Harmonious Subsequence easy or hard?
Longest Harmonious Subsequence is classified as an Easy problem on LeetCode with an acceptance rate around 64%. The challenge mainly involves recognizing that only counts of consecutive numbers matter, making a hash map frequency approach ideal.
How to solve Longest Harmonious Subsequence in O(n)?
Count the occurrences of each number using a hash map. Then iterate through the keys and check if the map contains key+1. If it does, combine their frequencies to form a harmonious subsequence and update the maximum length.
What is the best approach for Longest Harmonious Subsequence?
The most efficient approach uses a hash map to count the frequency of each number. For every value x, check whether x+1 exists and compute count[x] + count[x+1]. This finds the longest harmonious subsequence in O(n) time with O(n) space.
What data structure is used in Longest Harmonious Subsequence?
A hash table (hash map) is the primary data structure used in the optimal solution. It stores the frequency of each number and enables constant-time lookups when checking for adjacent values like x and x+1.
What is the time complexity of Longest Harmonious Subsequence?
The optimal hash map solution runs in O(n) time because it scans the array once to build frequencies and once more to check adjacent values. The sorting-based solution takes O(n log n) due to the initial sort.
Longest Harmonious Subsequence Python or Java solution approach?
Both Python and Java implementations follow the same idea: build a frequency map using a dictionary or HashMap, then iterate through the keys to check pairs of consecutive numbers. The algorithm runs in O(n) time and O(n) space.
Is Longest Harmonious Subsequence asked at Google, Amazon, or Meta?
This problem represents a common interview pattern involving frequency counting and hash maps. Variants of similar array counting questions appear in interviews at companies like Amazon and Google because they test understanding of hash tables and linear-time optimization.