Problem Description
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.
Key Insights
- A harmonious subsequence requires the maximum and minimum values to differ by exactly 1.
- We can leverage a frequency map (hash table) to count occurrences of each number.
- The solution involves checking pairs of consecutive integers and calculating the potential harmonious subsequence length.
- The longest length will be found by summing the counts of these pairs.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve the problem, we can use a hash table to count the occurrences of each number in the input array. We then iterate through the keys in the hash table, checking each key and its consecutive integer (key + 1). By summing their counts, we can determine the length of the harmonious subsequence for that pair. The maximum length found during this process will be our answer.