{x}
blog image

Longest Harmonious Subsequence

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.

 

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.

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -109 <= nums[i] <= 109

Solution Explanation: Longest Harmonious Subsequence

The problem asks to find the length of the longest harmonious subsequence within a given integer array nums. A harmonious subsequence is defined as a subsequence where the difference between the maximum and minimum values is exactly 1.

Approach:

The most efficient approach utilizes a hash table (or dictionary in Python) to count the occurrences of each number in the input array. We then iterate through the counts: for each number x, we check if x + 1 also exists in the counts. If it does, the combined count of x and x + 1 represents a harmonious subsequence. We keep track of the maximum length encountered during this iteration.

Time Complexity: O(n), where n is the length of the input array. This is because we iterate through the array once to count occurrences and then iterate through the unique numbers (at most n) in the hash table.

Space Complexity: O(k), where k is the number of unique elements in the input array. In the worst case, k could be n (all elements are unique). This accounts for the space used by the hash table to store the counts.

Code Implementation (Python):

from collections import Counter
 
class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = Counter(nums) #Efficiently counts element occurrences
        max_length = 0
        for num in count:
            if num + 1 in count: #Check if a harmonious pair exists
                max_length = max(max_length, count[num] + count[num + 1])
        return max_length

Code Implementation (Java):

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

Code Implementation (C++):

#include <unordered_map>
#include <algorithm>
 
class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        int max_length = 0;
        for (auto const& [num, freq] : count) {
            if (count.count(num + 1)) {
                max_length = max(max_length, freq + count[num + 1]);
            }
        }
        return max_length;
    }
};

Code Implementation (JavaScript):

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function(nums) {
    const count = {};
    for (const num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    let maxLength = 0;
    for (const num in count) {
        const numInt = parseInt(num);
        if (count.hasOwnProperty(numInt + 1)) {
            maxLength = Math.max(maxLength, count[numInt] + count[numInt + 1]);
        }
    }
    return maxLength;
};

Code Implementation (Go):

func findLHS(nums []int) int {
	counts := make(map[int]int)
	for _, num := range nums {
		counts[num]++
	}
	maxLength := 0
	for num, freq := range counts {
		if freq2, ok := counts[num+1]; ok {
			maxLength = max(maxLength, freq+freq2)
		}
	}
	return maxLength
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These code examples all follow the same basic algorithm and achieve the optimal time and space complexity. The choice of language depends on personal preference and the context of the application.