algoadvance

Leetcode 594. Longest Harmonious Subsequence

Problem Statement

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

A harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

A subsequence of an 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.

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 subsequence is [1,2] or [2,3] or [3,4].

Example 3:

Input: nums = [1,1,1,1]
Output: 0
Explanation: There is no harmonious subsequence since all elements are the same.

Clarifying Questions

1. What is the range of the input size?
   • The number of elements in the given array (nums) can be up to (10^4).
2. What is the range of the values in the array?
   • Each element in the array (nums[i]) is in the range of ([-10^4, 10^4]).
3. Is the input array always non-empty?
   • Yes, the input array will always contain at least one element.
4. Can the elements of the array be negative?
   • Yes, elements can be negative, as they range from (-10^4) to (10^4).

Strategy

1. Use a Hash Map to Count Frequencies:
   • We will use an unordered_map (or hash_map) to keep track of the frequency of each element in the array.
2. Check for Harmonious Subsequences:
   • For each unique number in the hash map, if the next consecutive number (num + 1) exists in the map, we can potentially form a harmonious subsequence. The length of this subsequence would be the sum of the frequencies of these two numbers.
3. Update Maximum Length:
   • We will maintain a variable to keep track of the maximum length of any harmonious subsequence found.
4. Edge Case:
   • If no harmonious subsequence is found (all elements are the same or the differences are greater than 1), the result is 0.

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> frequency;
        
        // Count the frequency of each element
        for (int num : nums) {
            frequency[num]++;
        }
        
        int maxLength = 0;
        
        // Check each key in the map
        for (auto& entry : frequency) {
            int num = entry.first;
            if (frequency.find(num + 1) != frequency.end()) {
                // Potential harmonious subsequence length
                int currentLength = frequency[num] + frequency[num + 1];
                maxLength = max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
};

Time Complexity

• Building the Hash Map: O(n), where n is the number of elements in nums.
• Iterating through the Hash Map: O(k), where k is the number of unique elements.
• Given that k can be at most n (in the worst case where all elements are unique), the overall time complexity is O(n).

Space Complexity

• The space complexity is O(n) for the hash map storing the frequencies of the elements.

This solution is efficient given the constraints and ensures we check all potential harmonious subsequences in linear time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?