Sponsored
Sponsored
This approach leverages a map (or dictionary in Python) to count the frequency of each number in the array. Once we know the count of each number, we can iterate through the keys and check for pairs of consecutive numbers (n and n+1). The length of a harmonious subsequence that can be formed is the sum of the counts of these consecutive numbers.
Time Complexity: O(n), Space Complexity: O(n)
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int findLHS(int* nums, int numsSize){
6 int map[2000000000] = {0}, offset = 1000000000;
7 int maxLength = 0;
8
9 for(int i = 0; i < numsSize; i++) {
10 map[nums[i] + offset]++;
11 }
12
13 for(int i = 0; i < 2000000000; i++) {
14 if(map[i] > 0 && map[i+1] > 0) {
15 int currentLength = map[i] + map[i+1];
16 if (currentLength > maxLength) {
17 maxLength = currentLength;
18 }
19 }
20 }
21
22 return maxLength;
23}The C solution uses an array to act as a hashmap to count occurrences of numbers. A large integer array of size 2 billion is declared to accommodate the range of input, offset by 1 billion to handle negative values by shifting index.
An alternative approach would be to sort the numbers. After sorting, we can use a two-pointer technique to find the longest subsequence where the difference between the smallest and largest value is exactly one. This method may be less efficient due to the sorting step but provides a straightforward solution.
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) if counting sort or constant space partition approach is used.
1#include <algorithm>
using namespace std;
int findLHS(vector<int>& nums) {
sort(nums.begin(), nums.end());
int left = 0, maxLength = 0;
for (int right = 1; right < nums.size(); ++right) {
while (nums[right] - nums[left] > 1) {
++left;
}
if (nums[right] - nums[left] == 1) {
maxLength = max(maxLength, right - left + 1);
}
}
return maxLength;
}This C++ solution sorts the input and then applies the two-pointer approach to calculate the longest harmonious subsequence of consecutive elements.