594. Longest Harmonious Subsequence

Array Hash Table Sliding Window Counting

Time: O(n)

Space: O(n)

Intuition

A harmonious subsequence uses elements whose max and min differ by exactly 1. For each value v, the subsequence of v and v+1 has length freq[v]+freq[v+1].

Algorithm

1Build frequency map.
2For each key v, if freq[v+1] exists, candidate = freq[v] + freq[v+1].
3Return max candidate.

Example Walkthrough

Input: [1,3,2,2,5,2,3,7]

1.freq={1:1,2:3,3:2,5:1,7:1}.
2.1+2: 1+3=4. 2+3: 3+2=5.

Output: 5

Common Pitfalls

•Only check v+1 (not v-1) to avoid double-counting.

594.cs

// Approach: Frequency HashMap; for each distinct value, if value+1 also
// exists combine their counts for a candidate harmonious length.
// Time: O(n) Space: O(n)

public class Solution
{
    public int FindLHS(int[] nums)
    {
        // Create a Dictionary to keep track of the frequency of each number
        Dictionary<int, int> frequencyMap = new Dictionary<int, int>();

        // Count the occurrences of each number in the array.
        foreach (int num in nums)
        {
            if (frequencyMap.ContainsKey(num))
                frequencyMap[num]++;
            else
                frequencyMap[num] = 1;
        }

        // Initialize variable to keep track of the longest harmonious subsequence
        int longestHarmoniousSubsequence = 0;

        // Iterate through the numbers in the array
        foreach (int num in nums)
        {
            // Check if the number that is one more than the current number exists in the map
            if (frequencyMap.ContainsKey(num + 1))
            {
                // If it exists, calculate the sum of the frequencies of the current number
                // and the number that is one more than the current number
                int currentLength = frequencyMap[num] + frequencyMap[num + 1];

                // Update the longest harmonious subsequence if the current sum is greater
                longestHarmoniousSubsequence = Math.Max(longestHarmoniousSubsequence, currentLength);
            }
        }

        // Return the length of the longest harmonious subsequence found
        return longestHarmoniousSubsequence;
    }
}

Was this solution helpful?