LeetCode 594 - Longest Harmonious Subsequence

The problem asks us to find the length of the longest harmonious subsequence in an integer array. A harmonious array is defined as one where the difference between the maximum and minimum values is exactly 1.

leetcodeeasyarrayhash-tablesliding-windowsortingcounting

LeetCode Problem 594

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sliding Window, Sorting, Counting

Solution

Problem Understanding

The problem asks us to find the length of the longest harmonious subsequence in an integer array. A harmonious array is defined as one where the difference between the maximum and minimum values is exactly 1. In simpler terms, given an array nums, we are searching for the longest collection of elements where the largest element is exactly one more than the smallest element, and all other elements are either the maximum or the minimum of this subsequence. The subsequence does not need to be contiguous, so elements can be scattered across the array.

The input is a list of integers with length between 1 and 20,000, and integer values can range from -10^9 to 10^9. The output is a single integer representing the length of the longest harmonious subsequence. If no harmonious subsequence exists (i.e., no two numbers differ by exactly 1), the output should be 0.

Important edge cases include arrays where all elements are the same (no harmonious subsequence), arrays with only two distinct numbers that differ by more than 1, and arrays with repeated numbers where multiple candidate subsequences exist.

Approaches

A brute-force approach would generate all possible subsequences of the array, check the maximum and minimum of each subsequence, and record the length if it forms a harmonious subsequence. This guarantees correctness but is extremely inefficient because the number of subsequences grows exponentially with the array size, making it infeasible for large inputs.

The key insight for an optimal solution is to recognize that we only care about the frequency of each number and its immediate neighbor (number ±1). If we count how many times each number occurs, we can iterate over the unique numbers and check if number + 1 exists. If it does, the sum of the counts of number and number + 1 gives the length of a candidate harmonious subsequence. This approach reduces the problem to counting frequencies and scanning the keys, which is efficient even for large arrays.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generates all subsequences and checks max-min difference, impractical for large inputs
Optimal O(n) O(n) Counts frequencies using a hash map, then checks each number with its neighbor

Algorithm Walkthrough

  1. Initialize an empty hash map (count) to store the frequency of each integer in the array.
  2. Iterate through the array nums and populate the count map so that each key maps to the number of times it appears.
  3. Initialize a variable max_length to 0 to track the length of the longest harmonious subsequence found.
  4. Iterate over each unique number num in the count map.
  5. For each num, check if num + 1 exists in the map.
  6. If it exists, calculate the combined length count[num] + count[num + 1].
  7. Update max_length if this combined length is larger than the current max_length.
  8. After checking all numbers, return max_length.

Why it works: The algorithm works because a harmonious subsequence must consist of exactly two adjacent integer values. By counting frequencies and checking only num and num + 1, we ensure that we consider every potential harmonious subsequence exactly once, and we sum all occurrences of these two values to get the longest possible length.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        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_length

In this implementation, we use Counter from Python's collections module to quickly count frequencies. We then iterate through the keys of the counter, check if the consecutive number exists, and update the maximum length found. This is a direct implementation of the algorithm walkthrough.

Go Solution

func findLHS(nums []int) int {
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }
    
    maxLength := 0
    for num, freq := range count {
        if freqNext, exists := count[num+1]; exists {
            if freq+freqNext > maxLength {
                maxLength = freq + freqNext
            }
        }
    }
    
    return maxLength
}

In Go, we use a map[int]int to count the frequency of each number. The rest of the logic is analogous to the Python version. We check if num + 1 exists in the map, sum the counts, and update the maximum length. Go does not have a built-in counter, so we manually increment the map values.

Worked Examples

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

Step Operation Count Map max_length
1 Count frequencies {1:1,2:3,3:2,5:1,7:1} 0
2 num=1, check 2 1+3=4 max_length=4
3 num=2, check 3 3+2=5 max_length=5
4 num=3, check 4 4 does not exist max_length=5
5 num=5, check 6 6 does not exist max_length=5
6 num=7, check 8 8 does not exist max_length=5

Output: 5

Example 2: nums = [1,2,3,4]

Step Operation Count Map max_length
1 Count frequencies {1:1,2:1,3:1,4:1} 0
2 num=1, check 2 1+1=2 max_length=2
3 num=2, check 3 1+1=2 max_length=2
4 num=3, check 4 1+1=2 max_length=2

Output: 2

Example 3: nums = [1,1,1,1]

All numbers are the same, no consecutive numbers exist.

Output: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Count frequencies in O(n), then iterate through keys in O(n)
Space O(n) Store counts of each unique number, worst case all numbers distinct

Counting frequencies is linear in the size of the array, and scanning the map keys is also linear in the number of unique elements, which is at most n. Space is linear to store the counts.

Test Cases

# Provided examples
assert Solution().findLHS([1,3,2,2,5,2,3,7]) == 5  # Example 1
assert Solution().findLHS([1,2,3,4]) == 2          # Example 2
assert Solution().findLHS([1,1,1,1]) == 0          # Example 3

# Additional cases
assert Solution().findLHS([1,2,2,1]) == 4          # simple repeated numbers
assert Solution().findLHS([1]) == 0                # single element
assert Solution().findLHS([1,3,5,7]) == 0          # no harmonious subsequence
assert Solution().findLHS([-1,0,0,-1,-1,0,1,1]) == 6 # negative numbers with +1 difference
assert Solution().findLHS([1000000000,999999999]) == 2 # large numbers
Test Why
[1,3,2,2,5,2,3,7] Standard case with multiple candidates, picks longest subsequence
[1,2,3,4] Multiple pairs of consecutive numbers with length 2
[1,1,1,1] All numbers same, no harmonious subsequence
[1,2,2,1] Checks repeated numbers forming a full subsequence
[1] Minimal length array, edge case
[1,3,5,7] No consecutive numbers, should return 0
[-1,0,0,-1,-1,0,1,1] Negative numbers, ensure algorithm handles negatives correctly
[1000000000,999999999] Large values, checks handling of integer extremes

Edge Cases

All elements identical: For example, [1,1,1,1]. Since a harmonious subsequence requires a difference of exactly 1, an array with identical elements should return 0. The implementation correctly checks for num + 1 existence, so no update occurs.

Single element array: [1]. A single-element array cannot form a harmonious subsequence, so the algorithm returns 0. The count map will have one key, and `num +