Longest Harmonious Subsequence

Longest Harmonious Subsequence

What is this problem about?

The Longest Harmonious Subsequence problem gives you an integer array and asks you to find the length of the longest possible subsequence that is "harmonious." A harmonious array is defined as an array where the difference between its absolute maximum value and its absolute minimum value is exactly 1. Because it's a subsequence, you can pick elements from anywhere in the array, ignoring their original order.

Why is this asked in interviews?

This is a very common warm-up or early-stage interview question because it gracefully tests a candidate's ability to transition from an $O(N \log N)$ sorting mindset to a faster $O(N)$ hash map mindset. It evaluates your understanding of frequencies, combinations, and how to use dictionaries to pair related data.

Algorithmic pattern used

The most efficient approach uses the Hash Table / Counting pattern. Because the difference between the max and min must be exactly 1, a harmonious subsequence can only ever consist of two adjacent integers, like X and X + 1. By creating a frequency map of all numbers in the array, you can simply iterate through the unique numbers. For any number num, if num + 1 also exists in the map, the length of their harmonious subsequence is exactly count(num) + count(num + 1).

Example explanation

Consider the array [1, 3, 2, 2, 5, 2, 3, 7]. First, we build a frequency map:

• 1: 1
• 2: 3
• 3: 2
• 5: 1
• 7: 1

Now we iterate through the keys in our map:

• Key 1: Does 2 exist? Yes. Length = count(1) + count(2) = $1 + 3 = 4$.
• Key 2: Does 3 exist? Yes. Length = count(2) + count(3) = $3 + 2 = 5$.
• Key 3: Does 4 exist? No.
• Key 5: Does 6 exist? No.
• Key 7: Does 8 exist? No.

The maximum length found is 5 (which corresponds to picking all the 2s and 3s: [3, 2, 2, 2, 3]).

Common mistakes candidates make

A frequent mistake candidates make is assuming a harmonious array can have a difference less than or equal to 1, meaning they count sequences made of just a single repeating number (e.g., all 2s). The prompt strictly states the difference must be exactly 1. Therefore, you must verify that num + 1 actually exists in the map before adding their counts together!

Interview preparation tip

For the Longest Harmonious Subsequence interview pattern, always prioritize the Hash Map solution over sorting. While sorting the array and using a sliding window works in $O(N \log N)$ time, the Hash Map achieves $O(N)$ time. When asked about subsequences where order doesn't matter and relationships are based on values (like $X$ and $X+1$), a frequency dictionary should always be your first instinct.