Longest Harmonious Subsequence
On this page 
Problem Statement Solution 1: Using a Hash Map Solution 2: Sorting and Two-Pointer Approach Solution 3: Frequency Map with Iteration Solution 4: Sorting and Set Approach Solution 5: Using Array Frequency Count Solution 6: Sorting with Binary Search Solution 7: Using Map with Max Calculation Solution 8: Using Set and Array Count Solution 9: Hash Table with Frequency Count Solution 10: Sorting with Two-Pointer and Hash Map More Problems Solutions
Problem Statement
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.
Example 1
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Example 2
Input: nums = [1,2,3,4]
Output: 2
Example 3
Input: nums = [1,1,1,1]
Output: 0
Constraints
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.
Solution 1: Using a Hash Map
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
Solution 2: Sorting and Two-Pointer Approach
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
Solution 3: Frequency Map with Iteration
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
Solution 4: Sorting and Set Approach
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
Solution 5: Using Array Frequency Count
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
Solution 6: Sorting with Binary Search
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
Solution 7: Using Map with Max Calculation
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
Solution 8: Using Set and Array Count
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
Solution 9: Hash Table with Frequency Count
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
Solution 10: Sorting with Two-Pointer and Hash Map
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