Longest Harmonious Subsequence: Counting Adjacent Value Pairs

LeetCode 594. Longest Harmonious Subsequence asks you to find the longest subsequence of an array where the difference between the maximum and minimum value is exactly 1. That subsequence is called "harmonious." You can pick elements from anywhere in the array (they do not need to be contiguous), but the max and min of your chosen elements must differ by exactly 1. If no such subsequence exists, return 0.

Why this problem matters

At first glance this looks like it might need some kind of sliding window or sorting trick. But once you reframe the question, it becomes much simpler. A harmonious subsequence can only contain two distinct values, and those two values must differ by exactly 1. So you are really asking: "For each pair of consecutive integers (k, k+1), how many total occurrences do they have in the array?"

That reframing turns the problem into a frequency counting exercise, which is one of the most common patterns in hash map problems. You will see the same "count first, then query pairs" strategy in problems like Subarray Sum Equals K, Group Anagrams, and Top K Frequent Elements. Mastering it here, in a simpler context, makes those harder problems feel familiar.

This is also a great example of how choosing the right data structure collapses complexity. Without a hash map, you would need to sort the array or use nested loops. With a hash map, you get a clean O(n) solution in just a few lines.

The approach

Build a frequency map of every value in the array. Then iterate through each key in the map and check whether key + 1 also exists. If it does, the harmonious subsequence for that pair has length count[key] + count[key + 1]. Track the maximum across all pairs.

from collections import Counter

def findLHS(nums):
    count = Counter(nums)
    longest = 0

    for num in count:
        if num + 1 in count:
            longest = max(longest, count[num] + count[num + 1])

    return longest

Here is why this works:

• Counter(nums) builds a dictionary mapping each value to how many times it appears. This takes O(n) time.
• For each key, you only check key + 1, not key - 1. This avoids double-counting pairs. If both 2 and 3 exist, you will find the pair when processing key=2.
• max(longest, ...) keeps a running maximum. At the end, longest holds the answer.
• If no key has a neighbor at key + 1, longest stays at 0, which is the correct return value for arrays with no harmonious subsequence.

Step-by-step walkthrough

Let's trace through nums = [1, 3, 2, 2, 5, 2, 3, 7] to see exactly how the algorithm finds the answer.

After checking every key in the frequency map, the best pair is (2, 3) with a combined count of 5. That is our answer.

Complexity analysis

Edge cases to watch for

• All elements are the same - e.g. [1, 1, 1, 1]. No pair (k, k+1) exists because there is only one distinct value. The answer is 0, not 4. A harmonious subsequence requires the max and min to differ by exactly 1, not 0.
• Empty array - return 0. The Counter will be empty and the loop never executes.
• Two elements differing by 1 - e.g. [1, 2]. The answer is 2. This is the smallest valid harmonious subsequence.
• Negative numbers - the algorithm works identically since Counter and num + 1 handle negatives. For example, [-1, 0, -1] gives 3.
• Large gaps between values - e.g. [1, 100, 200]. No adjacent pairs exist, so the answer is 0. The hash map lookup for num + 1 simply returns false for each key.

The building blocks

This problem is built on two reusable pieces that show up across many hash map problems:

1. Frequency counting with a hash map

The act of counting occurrences is one of the most fundamental hash map operations. You will use Counter or a manual dictionary in problems ranging from anagram detection to bucket sort. The pattern is always the same: iterate once, increment counts, then query the map.

2. Querying neighbor keys

After building the frequency map, you check whether a related key exists. Here it is num + 1. In Two Sum it is target - num. In Longest Consecutive Sequence it is num - 1 to find chain starts. The shape of the query changes, but the principle stays the same: use O(1) hash map lookups to avoid nested iteration.

These two pieces combine cleanly in this problem. Learning to separate "build the map" from "query the map" will help you decompose harder problems like Subarray Sum Equals K and Longest Consecutive Sequence, where the query step is more involved.

From understanding to recall

Reading through this solution once is enough to understand the idea. But understanding and recalling under pressure are two different things. A week from now, if you see a problem that requires frequency counting plus neighbor lookups, will the pattern fire automatically?

That is the gap spaced repetition fills. By drilling the frequency-count-then-query pattern as a standalone building block, you train yourself to recognize it instantly. After a few review cycles, you will not need to re-derive the approach from scratch. The code will be in your fingers, ready to adapt to whatever variation the problem throws at you.

Related posts

• Contains Duplicate - the simplest hash set problem, introducing the idea of O(1) membership lookups
• Longest Consecutive Sequence - another frequency map problem where you query neighbor keys to build chains
• Subarray Sum Equals K - uses a prefix sum hash map with a similar "build then query" structure