Longest Harmonious Subsequence

Difficulty: Easy | Acceptance: 64.60% | Paid: No Topics: Array, Hash Table, Sliding Window, Sorting, Counting

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 of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

• Examples
• Constraints
• Brute Force
• Sorting + Two Pointers
• Hash Map Frequency Count

Examples

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

Input: nums = [1,2,3,4]
Output: 2

Input: nums = [1,1,1,1]
Output: 0

Constraints

- 1 <= nums.length <= 2 * 10^4
- -10^9 <= nums[i] <= 10^9

Brute Force

Intuition For each element, treat it as the minimum value and count all elements that are either equal to it or exactly one greater. Track the maximum count where both values exist.

Steps

• Iterate through each element as a potential minimum value
• For each minimum, count elements equal to it or equal to minimum + 1
• Track if both values exist in the count
• Update the maximum length when both values are present

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        max_len = 0
        n = len(nums)
        for i in range(n):
            count = 0
            has_min = False
            has_max = False
            for j in range(n):
                if nums[j] == nums[i] or nums[j] == nums[i] + 1:
                    count += 1
                    if nums[j] == nums[i]:
                        has_min = True
                    else:
                        has_max = True
            if has_min and has_max:
                max_len = max(max_len, count)
        return max_len

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large inputs

Sorting + Two Pointers

Intuition Sort the array and use a sliding window to find the longest subarray where the difference between max and min is exactly 1.

Steps

• Sort the array in ascending order
• Use two pointers (left and right) to maintain a window
• Expand right pointer and shrink left pointer when difference exceeds 1
• Update max length when difference equals exactly 1

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums.sort()
        max_len = 0
        n = len(nums)
        left = 0
        
        for right in range(n):
            while nums[right] - nums[left] > 1:
                left += 1
            if nums[right] - nums[left] == 1:
                max_len = max(max_len, right - left + 1)
        
        return max_len

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on sorting implementation
• Notes: Better than brute force but requires sorting

Hash Map Frequency Count

Intuition Count the frequency of each number using a hash map, then for each number check if number+1 exists. The harmonious subsequence length is the sum of their frequencies.

Steps

• Build a frequency map of all numbers in the array
• For each unique number in the map, check if number+1 exists
• If it exists, calculate the sum of frequencies of both numbers
• Return the maximum such sum found

from collections import Counter

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

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Most efficient approach with linear time complexity