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
My Solution
We can solve this problem by first sorting the array and then using the sliding window technique. We start with i and j equal to index 0 and we keep track of the maximum element so far as well as the minimum element, which are just the elements at positions j and i respectively, since we have sorted the array. If the difference between max and min is less than or equal to 1, we move j forward, updating our longest subsequence count if the difference is exactly 1. Otherwise if the difference between max and min is more than 1, we keep incrementing i until the difference is equal to 1 or i is equal to j. We return the longest subsequence after iterating through the array.
Time complexity is O(n * log n) due to the sorting. Space complexity is O(1) since we only require constant extra space.
class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
if (n == 1) {
return 0;
}
int i = 0;
int j = 0;
int max = nums[j];
int min = nums[i];
int longest = 0;
while (j < n) {
if (max-min <= 1) {
if (max-min == 1) {
longest = Math.max(longest, j-i+1);
}
j++;
if (j < n) {
max = nums[j];
}
}
else {
while (i != j && max-min > 1) {
i++;
min = nums[i];
}
}
}
return longest;
}
}