How do you solve Longest Harmonious Subsequence?

Build a frequency map of all numbers. For each number, check if num + 1 exists in the map. If it does, calculate the sum of their frequencies and update the maximum length accordingly. Return the maximum length found.

Longest Harmonious Subsequence

Q: What is the time complexity of Longest Harmonious Subsequence?

O(n). The algorithm makes a single pass to build the frequency map and then iterates over the unique keys once, resulting in linear time relative to the input size.

Q: What pattern does Longest Harmonious Subsequence use?

The Pattern: Hash Maps (Frequency Counting and Complement Lookup) The Heuristic: When a problem involves counting occurrences and checking relationships between elements differing by a fixed value, use a hash map to store frequencies and perform O(1) lookups for complements to efficiently find valid pairs.

Easy Hash Maps

Problem

Given an integer array nums, return the length of its longest harmonious subsequence where the difference between its maximum and minimum elements is exactly 1.

1 ≤ nums.length ≤ 2 * 10⁴
−10⁹ ≤ nums[i] ≤ 10⁹

Example

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

Output: 5

The longest harmonious subsequence is [3,2,2,2,3]. The algorithm first counts the frequency of each number: {1:1, 2:3, 3:2, 5:1, 7:1}. It then checks pairs of numbers differing by exactly 1. For the pair (2,3), the combined frequency is 3 + 2 = 5, which is the maximum. This approach avoids checking all subsequences explicitly, which would be computationally infeasible.

Approach

Straightforward Solution

A brute-force approach would consider all subsequences and check their max-min difference, resulting in exponential time complexity, which is impractical for large inputs.

Core Observation

The problem reduces to finding two numbers with a difference of exactly 1 whose combined frequency in the array is maximized. This is because any harmonious subsequence must consist of only these two numbers.

Path to Optimal

Preview

By counting the frequency of each unique number using a hash map, the problem transforms into iterating over keys and checking if the adjacent number (num + 1) exists. Summing their frequencies gives the length of a harmonious subsequence formed by those two numbers…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build a frequency map of all numbers. For each number, check if num + 1 exists in the map…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass to build the frequency map and then iterates over the unique keys once, resulting in linear time relative to the input size.

Space

O(n)

The frequency map stores counts for each unique number in the input, which in the worst case can be all distinct elements, requiring O(n) auxiliary space.

Pattern Spotlight

Hash Maps (Frequency Counting and Complement Lookup)

When a problem involves counting occurrences and checking relationships between elements differing by a fixed value, use a hash map to store frequencies and perform O(1) lookups for complements to efficiently find valid pairs.

Solution

Python

1class Solution:
2    def findLHS(self, nums: list[int]) -> int:
3        counts = {}
4
5        for num in nums:
6            counts[num] = counts.get(num, 0) + 1
7
8        max_length = 0
9
10        for num in counts:
11            if num + 1 in counts:
12                current_length = counts[num] + counts[num + 1]
13                max_length = max(max_length, current_length)
14
15        return max_length

Step-by-Step Solution

Build Frequency Map of All Numbers

3counts = {}
5for num in nums:
6    counts[num] = counts.get(num, 0) + 1

Objective

To count the occurrences of each unique number in the input array.

Key Insight

Counting frequencies transforms the problem from searching subsequences to analyzing number counts. This enables constant-time lookups for any number's frequency, which is essential for efficiently checking pairs differing by 1.

Interview Quick-Check

Core Logic

The frequency map stores each number as a key and its count as the value, enabling O(1) average-time lookups.

Common Pitfalls & Bugs

Forgetting to initialize counts properly or using inefficient data structures can degrade performance.

Identify and Track Maximum Length of Harmonious Subsequences

To iterate over the frequency map and find the maximum combined frequency of pairs of numbers differing by exactly 1.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 6 Critical

counts[num] = counts.get(num, 0) + 1

Increment the count for the current number in the frequency map.

This line's placement inside the loop ensures accurate frequency counts; using get with default 0 avoids key errors and simplifies counting logic.

Line 11 Critical

if num + 1 in counts:

Check if the adjacent number (num + 1) exists in the frequency map.

This check is critical to avoid key errors and to ensure only valid pairs are considered, directly enabling the core logic of the solution.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does checking only pairs of numbers differing by exactly 1 suffice to find the longest harmonious subsequence?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Longest Harmonious Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest Harmonious Subsequence drill

or drill a free problem

1	`class Solution:`
2	`def findLHS(self, nums: list[int]) -> int:`
3	`counts = {}`
4
5	`for num in nums:`
6	`counts[num] = counts.get(num, 0) + 1`
7
8	`max_length = 0`
9
10	`for num in counts:`
11	`if num + 1 in counts:`
12	`current_length = counts[num] + counts[num + 1]`
13	`max_length = max(max_length, current_length)`
14
15	`return max_length`