Longest Harmonious Subsequence

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.

link text

Clues

1. diff(arr[max], arr[min]) = 1 => make it adjacent! (sorting)
2. longest subsequence => You can skip quite many cases while you are building current the longest one.

Time Complexity

• Best Case: O(N)
• Average Case:
• Worst Case:

Space Complexity

• O(1) for iterative approach, I didn’t any data structure, sorted it in place.

My Implementation

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function(nums) {
    let max_length = 0;
    nums.sort((a,b)=> a-b)
    let i=0, j = 0
    j++;
    while(j < nums.length){
        if(nums[i] == nums[j]){
            j++
            continue;
        }
        else if(nums[j] - nums[i]==0){
            j++
            continue;
        }else if(nums[j] - nums[i] == 1) {
            max_length = Math.max(max_length, j - i + 1)
            j++;
            continue;
        }else{
            i++;
            continue
        }
    }
    return max_length
};

Better Implementation

var findLHS = function(nums) {
    nums.sort((a, b) => a - b);
    let j = 0, maxLength = 0;

    for (let i = 0; i < nums.length; i++) {
        while (nums[i] - nums[j] > 1) j++;
        if (nums[i] - nums[j] === 1) {
            maxLength = Math.max(maxLength, i - j + 1);
        }
    }

    return maxLength;
};

Test cases

[1,1,1,1,1,3,5,5,6]
[1,2,2,1]
[1,1,1,1]
[1,2,3,4]
[1,3,2,2,5,2,3,7]