Problem Description

Given an array nums of integers, you are to find the length of its longest harmonious subsequence. A harmonious subsequence is a subsequence where the difference between its maximum and minimum values is exactly 1.

Constraints:

• You may not reorder the elements in nums.
• A subsequence can be formed by deleting some (or no) elements without changing the order of the remaining elements.
• Each element can be used at most once in the subsequence.
• Return the length of the longest harmonious subsequence found.

Thought Process

At first glance, one might consider generating all possible subsequences and checking if their maximum and minimum values differ by exactly 1. However, this brute-force approach is highly inefficient because the number of subsequences grows exponentially with the size of the array.

To optimize, we need to notice that the order of elements in a subsequence is preserved, but we can pick or skip any element. The core of the problem is to count the maximum number of elements that can be picked where all values are either n or n+1 (or n-1), for some integer n.

This leads us to focus on counting occurrences of each number and looking for pairs of numbers that differ by exactly 1. By summing the counts of such pairs, we can find the length of the longest harmonious subsequence.

Solution Approach

Here’s a step-by-step breakdown of the optimized solution:

1. Count occurrences: Use a hash map (dictionary) to count how many times each unique number appears in nums. This allows for O(1) lookups and efficient aggregation.
2. Find harmonious pairs: For each unique number n in the hash map, check if n+1 also exists. If it does, the combined count of n and n+1 represents a possible harmonious subsequence.
3. Track the maximum: Keep a variable to store the maximum length found as you iterate through all possible pairs.
4. Return the result: After checking all pairs, return the maximum length found.

We use a hash map because it allows us to efficiently count and check for the presence of harmonious pairs in O(1) time per operation, making the overall approach much faster than brute-force.

Example Walkthrough

Let’s walk through the sample input nums = [1,3,2,2,5,2,3,7]:

1. Count occurrences:
   • 1 appears once
   • 2 appears three times
   • 3 appears twice
   • 5 appears once
   • 7 appears once
   So, count = {1:1, 2:3, 3:2, 5:1, 7:1}
2. Check harmonious pairs:
   • For 1: 1+1=2 exists, so length is 1+3=4
   • For 2: 2+1=3 exists, so length is 3+2=5
   • For 3: 3+1=4 does not exist
   • For 5: 5+1=6 does not exist
   • For 7: 7+1=8 does not exist
3. Find the maximum:
   • Max length is 5 (from numbers 2 and 3)

Thus, the answer is 5.

Time and Space Complexity

Brute-force approach: Generating all possible subsequences is O(2ⁿ), which is infeasible for large n.

Optimized approach:

• Time Complexity: O(n), where n is the length of nums. Counting occurrences takes O(n), and iterating through the unique numbers (at most n) is also O(n).
• Space Complexity: O(n) for storing the counts in the hash map.

Summary

The key insight for solving the Longest Harmonious Subsequence problem is to recognize that we only need to count pairs of numbers that differ by 1 and sum their frequencies. Using a hash map for counting makes the solution both simple and efficient, reducing the problem from exponential to linear time. This approach is elegant because it leverages frequency counting and avoids unnecessary enumeration of subsequences.

Code Implementation

from collections import Counter

class Solution:
    def findLHS(self, nums):
        count = Counter(nums)
        max_len = 0
        for num in count:
            if num + 1 in count:
                max_len = max(max_len, count[num] + count[num + 1])
        return max_len
      

#include <unordered_map>
#include <vector>
#include <algorithm>

class Solution {
public:
    int findLHS(std::vector<int>& nums) {
        std::unordered_map<int, int> count;
        for (int n : nums) {
            count[n]++;
        }
        int max_len = 0;
        for (const auto& p : count) {
            int num = p.first;
            if (count.find(num + 1) != count.end()) {
                max_len = std::max(max_len, count[num] + count[num + 1]);
            }
        }
        return max_len;
    }
};
      

import java.util.HashMap;

class Solution {
    public int findLHS(int[] nums) {
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int n : nums) {
            count.put(n, count.getOrDefault(n, 0) + 1);
        }
        int maxLen = 0;
        for (int key : count.keySet()) {
            if (count.containsKey(key + 1)) {
                maxLen = Math.max(maxLen, count.get(key) + count.get(key + 1));
            }
        }
        return maxLen;
    }
}
      

var findLHS = function(nums) {
    const count = {};
    for (let n of nums) {
        count[n] = (count[n] || 0) + 1;
    }
    let maxLen = 0;
    for (let num in count) {
        let n = parseInt(num);
        if (count.hasOwnProperty(n + 1)) {
            maxLen = Math.max(maxLen, count[n] + count[n + 1]);
        }
    }
    return maxLen;
};