LeetCode 594: Longest Harmonious Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 594: Longest Harmonious Subsequence?

In LeetCode 594: Longest Harmonious Subsequence, you’re given an integer array nums, and your task is to return the length of the longest harmonious subsequence—a subsequence where the difference between the maximum and minimum values is exactly 1. A subsequence can be formed by picking elements in any order without changing their relative positions’ continuity requirement (unlike a subarray). For example, with nums = [1,3,2,2,5,2,3,7], the longest harmonious subsequence is [3,2,2,2,3] (length 5), as max (3) - min (2) = 1. This problem builds on LeetCode 1: Two Sum for hash map usage but focuses on finding maximum subsequence lengths with a specific difference constraint.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: Integer—length of longest harmonious subsequence.
• Rules: Subsequence max - min = 1; elements can be non-contiguous; return 0 if no such subsequence exists.

Constraints

• 1 <= nums.length <= 2 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

Examples

• Input: nums = [1,3,2,2,5,2,3,7]
• Output: 5
• Subsequence [3,2,2,2,3], max=3, min=2, length=5.
• Input: nums = [1,2,3,4]
• Output: 2
• Subsequence [1,2] or [2,3] or [3,4], length=2.
• Input: nums = [1,1,1,1]
• Output: 0
• No pair differs by 1.

Understanding the Problem: Finding the Harmonious Stretch

To solve LeetCode 594: Longest Harmonious Subsequence in Python, we need to find the longest subsequence in an array where the maximum and minimum values differ by exactly 1, handling up to 2 * 10⁴ elements efficiently. A brute-force approach checking all possible subsequences (O(2^n)) is impractical. Instead, a key insight—only consecutive integers (e.g., x and x+1) can form a harmonious subsequence—leads to a hash map solution that counts frequencies in O(n) time, checking pairs of consecutive numbers. We’ll explore:

• Best Solution (Hash Map with Frequency Counting): O(n) time, O(n) space—fast and optimal.
• Alternative Solution (Brute-Force Subsequence Checking): O(2^n) time, O(n) space—thorough but slow.

Let’s dive into the hash map solution with a friendly breakdown!

Best Solution: Hash Map with Frequency Counting

Why Hash Map Wins

The hash map with frequency counting solution is the best for LeetCode 594 because it finds the longest harmonious subsequence in O(n) time and O(n) space by building a frequency map of all numbers in one pass, then checking each number and its consecutive pair (x and x+1) to compute the maximum length efficiently. It’s like tallying votes for each number, then pairing neighbors to see who teams up best—all in a quick, clever count!

How It Works

Think of this as a number-pairing organizer:

• Step 1: Build Frequency Map:
• Use a hash map to count occurrences of each number in nums.
• Step 2: Check Consecutive Pairs:
• For each number x in the map:
• If x+1 exists, compute length = freq(x) + freq(x+1).
• Update maximum length if larger.
• Step 3: Return Result:
• Maximum length found (0 if no pairs).
• Why It Works:
• Harmonious subsequence must be two consecutive integers.
• Hash map enables O(1) frequency lookups.

It’s like a harmonious-pairing maestro!

Step-by-Step Example

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

• Step 1: Build frequency map:
• freq = {1: 1, 2: 3, 3: 2, 5: 1, 7: 1}.
• Step 2: Check pairs:
• 1: 1+1=2 exists, length = 1 + 3 = 4.
• 2: 2+1=3 exists, length = 3 + 2 = 5.
• 3: 3+1=4 not present, skip.
• 5: 5+1=6 not present, skip.
• 7: 7+1=8 not present, skip.
• Max length = 5 (pair 2 and 3).
• Step 3: Return 5.
• Result: 5.

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

• Step 1: freq = {1: 1, 2: 1, 3: 1, 4: 1}.
• Step 2:
• 1: 1+1=2, length = 1 + 1 = 2.
• 2: 2+1=3, length = 1 + 1 = 2.
• 3: 3+1=4, length = 1 + 1 = 2.
• 4: 4+1=5, skip.
• Max length = 2.
• Step 3: Return 2.
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def findLHS(self, nums: List[int]) -> int:
        # Step 1: Build frequency map
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1

        # Step 2: Find max length of harmonious subsequence
        max_length = 0
        for x in freq:
            if x + 1 in freq:
                length = freq[x] + freq[x + 1]
                max_length = max(max_length, length)

        # Step 3: Return result
        return max_length

• Lines 4-6: Initialize hash map, count frequency of each number.
• Lines 9-13: Iterate map:
• Check if x+1 exists, compute length, update max.
• Line 16: Return longest harmonious length.
• Time Complexity: O(n)—single pass to build map and check pairs.
• Space Complexity: O(n)—hash map storage.

It’s like a frequency-pairing wizard!

Alternative Solution: Brute-Force Subsequence Checking

Why an Alternative Approach?

The brute-force subsequence checking approach generates all possible subsequences, checks each for the harmonious property (max - min = 1), and tracks the longest, running in O(2^n) time and O(n) space for recursion or storage. It’s thorough but impractical for large arrays, making it a good baseline for small inputs or understanding.

How It Works

Picture this as a subsequence-hunting brute:

• Step 1: Generate all subsequences (recursively or iteratively).
• Step 2: For each, compute max and min, check if difference is 1.
• Step 3: Track longest valid subsequence.
• Step 4: Return length.

It’s like a trial-and-error harmony seeker!

Step-by-Step Example

Example: nums = [1,2,3]

• Step 1: Subsequences: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].
• Step 2: Check:
• [1,2]: 2-1=1, length=2.
• [2,3]: 3-2=1, length=2.
• Others: Difference ≠ 1 or length < 2.
• Step 3: Max length = 2.
• Result: 2.

Code for Brute-Force Approach

Copy codeclass Solution:
    def findLHS(self, nums: List[int]) -> int:
        def is_harmonious(sub):
            if not sub:
                return False
            min_val, max_val = min(sub), max(sub)
            return max_val - min_val == 1

        def generate_subsequences(arr, index, curr, all_subs):
            if index == len(arr):
                if curr:
                    all_subs.append(curr[:])
                return
            # Exclude current element
            generate_subsequences(arr, index + 1, curr, all_subs)
            # Include current element
            curr.append(arr[index])
            generate_subsequences(arr, index + 1, curr, all_subs)
            curr.pop()

        # Generate all subsequences
        all_subs = []
        generate_subsequences(nums, 0, [], all_subs)

        # Find longest harmonious subsequence
        max_length = 0
        for sub in all_subs:
            if is_harmonious(sub):
                max_length = max(max_length, len(sub))

        return max_length

• Lines 3-7: Check if subsequence is harmonious.
• Lines 9-18: Recursively generate all subsequences.
• Lines 21-22: Build subsequence list.
• Lines 25-28: Find longest valid subsequence.
• Time Complexity: O(2^n)—exponential subsequence generation.
• Space Complexity: O(n)—recursion stack and storage.

It’s a brute-force harmony hunter!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n), O(n), fast and elegant.
• Cons: Requires frequency insight.
• Brute-Force (Alternative):
• Pros: O(2^n), O(n), exhaustive.
• Cons: Impractical for large n.

Hash map wins for efficiency!

Additional Examples and Edge Cases

• Single value: 0.
• No pairs: 0.
• All same: 0.

Hash map handles them all!

Complexity Recap

• Hash Map: Time O(n), Space O(n).
• Brute-Force: Time O(2^n), Space O(n).

Hash map’s the speed champ!

Key Takeaways

• Hash Map: Frequency finesse—learn at Python Basics!
• Brute-Force: Exhaustive search.
• Subsequences: Harmony is fun.
• Python: Map or brute, your pick!

Final Thoughts: Find That Harmony!

LeetCode 594: Longest Harmonious Subsequence in Python is a clever array challenge. Hash map with frequency counting is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 1: Two Sum or LeetCode 560: Subarray Sum Equals K. Ready to count? Head to Solve LeetCode 594 on LeetCode and find that harmonious stretch today!