LeetCode Daily Challenge-594. Longest Harmonious Subsequence(Easy)

• LeetCode Link
• Date: 30th June 2025

Tags: Hash Map, Frequency Counting, Array, Easy, Subsequence

---

Problem Overview

We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1. Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

A subsequence can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Examples

Example 1:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Example 2:

Input: nums = [1,2,3,4]
Output: 2
Explanation: The longest harmonious subsequences are [1,2], [2,3], and [3,4], all of which have a length of 2.

Example 3:

Input: nums = [1,1,1,1]
Output: 0
Explanation: No harmonic subsequence exists.

---

Key Insights

The breakthrough insight is that since our target harmonious array is dealing with the absolute value of its elements and since it's a subsequence of our numbers array, we don't need to worry about the order of numbers or their index. If all we care about is what numbers appear and not their order or index, then we should start by building a frequency map.

For a harmonious subsequence:

• Only two distinct values can exist: x and x+1
• The difference between max and min must be exactly 1
• Order doesn't matter since we're looking for subsequences

---

Solution Approach

Method 1: Optimal Hash Map Solution

The most efficient approach uses frequency counting:

from collections import Counter

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        # Count frequency of each number
        freq = Counter(nums)
        max_length = 0

        # Check each number and its consecutive number
        for num in freq:
            if num + 1 in freq:
                # Combine frequencies of consecutive numbers
                max_length = max(max_length, freq[num] + freq[num + 1])

        return max_length

Method 2: Single Pass Optimization

We can optimize further by checking for harmonious subsequences while building the frequency map:

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        freq = {}
        max_length = 0

        for num in nums:
            # Update frequency
            freq[num] = freq.get(num, 0) + 1

            # Check if we can form harmonious subsequence with num-1
            if num - 1 in freq:
                max_length = max(max_length, freq[num] + freq[num - 1])

            # Check if we can form harmonious subsequence with num+1
            if num + 1 in freq:
                max_length = max(max_length, freq[num] + freq[num + 1])

        return max_length

---

Algorithm Walkthrough

Let's trace through nums = [1,3,2,2,5,2,3,7]:

Step 1: Build Frequency Map

freq = {1: 1, 3: 2, 2: 3, 5: 1, 7: 1}

Step 2: Check Each Number

• num = 1: Check if 2 exists → Yes! Length = freq[1] + freq[2] = 1 + 3 = 4
• num = 3: Check if 4 exists → No, check if 2 exists → Yes! Length = freq[3] + freq[2] = 2 + 3 = 5
• num = 2: Check if 3 exists → Yes! Length = freq[2] + freq[3] = 3 + 2 = 5
• num = 5: Check if 6 exists → No, check if 4 exists → No
• num = 7: Check if 8 exists → No, check if 6 exists → No

Step 3: Result

Maximum length found: 5

The harmonious subsequence is [3,2,2,2,3] with:

• Min = 2, Max = 3
• Difference = 3 - 2 = 1 ✓

---

Alternative Approaches

Method 3: Sorting Approach

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums.sort()
        left = 0
        max_length = 0

        for right in range(len(nums)):
            # Shrink window if difference > 1
            while nums[right] - nums[left] > 1:
                left += 1

            # Check if we have exactly difference of 1
            if nums[right] - nums[left] == 1:
                max_length = max(max_length, right - left + 1)

        return max_length

Complexity: O(n log n) time, O(1) space

---

Why This Works

If a number x appears freq[x] times and its consecutive number x + 1 appears freq[x + 1] times, then we have a valid harmonious subsequence of length freq[x] + freq[x + 1].

The key observations:

1. Only two values matter: A harmonious array can only contain exactly two distinct values that differ by 1
2. Frequency is key: We don't care about positions, only how many times each value appears
3. Consecutive pairs: We only need to check pairs (x, x+1) for all x in the array

---

Complexity Analysis

Hash Map Approach (Optimal)

• Time Complexity: O(n)
  • Single pass to build frequency map: O(n)
  • Single pass through unique values: O(n)
• Space Complexity: O(n)
  • Hash map to store frequencies: O(n)

Single Pass Approach

• Time Complexity: O(n)
  • Single pass through array: O(n)
• Space Complexity: O(n)
  • Hash map to store frequencies: O(n)

Sorting Approach

• Time Complexity: O(n log n)
  • Sorting: O(n log n)
  • Two pointers: O(n)
• Space Complexity: O(1)
  • In-place sorting

---

Common Pitfalls

1. Forgetting the "exactly 1" constraint: The difference must be exactly 1, not at most 1
2. Including single-value subsequences: A harmonious subsequence must have both values present
3. Over-complicating with order: Since it's a subsequence problem, order doesn't matter for our counting approach

---

Related Problems

• LeetCode 1: Two Sum (Hash Map pattern)
• LeetCode 560: Subarray Sum Equals K (Frequency counting)
• LeetCode 1498: Number of Subsequences That Satisfy the Given Sum Condition (Two pointers + subsequences)

---

Key Takeaways

This problem beautifully demonstrates the power of hash maps for frequency analysis. The transformation from a potentially exponential brute force solution to a linear time solution showcases how understanding the problem constraints (difference of exactly 1) can lead to elegant optimizations.

The hash map approach is not only optimal in terms of time complexity but also intuitive once you realize that only the frequencies of consecutive numbers matter, not their positions in the original array.