Imagine you have a list of integers called nums. A subsequence of this list is defined as a sequence that can be derived by removing some or none of the elements from the list without changing the order of the remaining elements.
A subsequence is considered harmonious if the difference between its maximum and minimum values is exactly 1. Your goal is to determine the length of the longest possible harmonious subsequence within the given list.
To illustrate, if you have a list of integers, your task is to find the longest subsequence where the difference between the highest and lowest number is precisely 1.
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Input: nums = [1,2,3,4]
Output: 2
Input: nums = [1,1,1,1]
Output: 0
1 <= nums.length <= 20,000: The number of elements in the list will be between 1 and 20,000.
-10^9 <= nums[i] <= 10^9: Each element in the list can range from -1 billion to 1 billion.
function longestHarmoniousSubsequenceHashMap(nums) {
const frequency = {};
let maxLength = 0;
for (const num of nums) {
frequency[num] = (frequency[num] || 0) + 1;
}
for (const key of Object.keys(frequency)) {
const currentNum = parseInt(key);
if (frequency[currentNum + 1]) {
maxLength = Math.max(maxLength, frequency[currentNum] + frequency[currentNum + 1]);
}
}
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceHashMap(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceHashMap(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceHashMap(nums3); //output: 0
function longestHarmoniousSubsequenceTwoPointer(nums) {
nums.sort((a, b) => a - b);
let maxLength = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}
if (nums[right] - nums[left] === 1) {
maxLength = Math.max(maxLength, right - left + 1);
}
}
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceTwoPointer(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceTwoPointer(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceTwoPointer(nums3); //output: 0
function longestHarmoniousSubsequenceFrequencyMap(nums) {
const frequency = new Map();
let maxLength = 0;
nums.forEach(num => {
frequency.set(num, (frequency.get(num) || 0) + 1);
});
frequency.forEach((count, num) => {
if (frequency.has(num + 1)) {
maxLength = Math.max(maxLength, count + frequency.get(num + 1));
}
});
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceFrequencyMap(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceFrequencyMap(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceFrequencyMap(nums3); //output: 0
function longestHarmoniousSubsequenceSet(nums) {
const uniqueNums = new Set(nums);
let maxLength = 0;
uniqueNums.forEach(num => {
if (uniqueNums.has(num + 1)) {
const count = nums.filter(x => x === num).length + nums.filter(x => x === num + 1).length;
maxLength = Math.max(maxLength, count);
}
});
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceSet(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceSet(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceSet(nums3); //output: 0
function longestHarmoniousSubsequenceArrayCount(nums) {
const frequency = Array.from({length: 20001}, () => 0);
let maxLength = 0;
for (const num of nums) {
frequency[num + 10000]++;
}
for (let i = 0; i < frequency.length - 1; i++) {
if (frequency[i] > 0 && frequency[i + 1] > 0) {
maxLength = Math.max(maxLength, frequency[i] + frequency[i + 1]);
}
}
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceArrayCount(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceArrayCount(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceArrayCount(nums3); //output: 0
function longestHarmoniousSubsequenceBinarySearch(nums) {
nums.sort((a, b) => a - b);
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
const target = nums[i] + 1;
const index = binarySearch(nums, target);
if (index !== -1) {
maxLength = Math.max(maxLength, index - i + 1);
}
}
return maxLength;
}
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceBinarySearch(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceBinarySearch(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceBinarySearch(nums3); //output: 0
function longestHarmoniousSubsequenceMapMax(nums) {
const frequencyMap = new Map();
let maxLength = 0;
nums.forEach(num => frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1));
frequencyMap.forEach((count, num) => {
if (frequencyMap.has(num + 1)) {
maxLength = Math.max(maxLength, count + frequencyMap.get(num + 1));
}
});
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceMapMax(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceMapMax(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceMapMax(nums3); //output: 0
function longestHarmoniousSubsequenceSetArrayCount(nums) {
const numSet = new Set(nums);
let maxLength = 0;
numSet.forEach(num => {
if (numSet.has(num + 1)) {
const count = nums.filter(n => n === num).length + nums.filter(n => n === num + 1).length;
maxLength = Math.max(maxLength, count);
}
});
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceSetArrayCount(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceSetArrayCount(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceSetArrayCount(nums3); //output: 0
function longestHarmoniousSubsequenceHashTable(nums) {
const frequency = {};
let maxLength = 0;
for (const num of nums) {
frequency[num] = (frequency[num] || 0) + 1;
}
for (const num in frequency) {
const currentNum = Number(num);
if (frequency[currentNum + 1] !== undefined) {
maxLength = Math.max(maxLength, frequency[currentNum] + frequency[currentNum + 1]);
}
}
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceHashTable(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceHashTable(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceHashTable(nums3); //output: 0
function longestHarmoniousSubsequenceSortingAndHashMap(nums) {
nums.sort((a, b) => a - b);
const frequency = {};
let maxLength = 0;
nums.forEach(num => frequency[num] = (frequency[num] || 0) + 1);
nums.forEach(num => {
if (frequency[num + 1]) {
maxLength = Math.max(maxLength, frequency[num] + frequency[num + 1]);
}
});
return maxLength;
}
const nums1 = [1,3,2,2,5,2,3,7];
longestHarmoniousSubsequenceSortingAndHashMap(nums1); //output: 5
const nums2 = [1,2,3,4];
longestHarmoniousSubsequenceSortingAndHashMap(nums2); //output: 2
const nums3 = [1,1,1,1];
longestHarmoniousSubsequenceSortingAndHashMap(nums3); //output: 0