594. Longest Harmonious Subsequence

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 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

 

Solutions

Solution: Hash Map

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const findLHS = function (nums) {
  const countMap = new Map();
  let result = 0;

  for (const num of nums) {
    const count = countMap.get(num) ?? 0;

    countMap.set(num, count + 1);
  }

  for (const [num, count] of countMap) {
    if (!countMap.has(num + 1)) continue;
    const totalCount = count + countMap.get(num + 1);

    result = Math.max(totalCount, result);
  }

  return result;
};