*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #594 (*Easy*): 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 subsequence among all its possible subsequences.*

*A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.*

*Examples:*

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 |

Example 3: | |
---|---|

Input: |
nums = [1,1,1,1] |

Output: |
0 |

*Constraints:*

- 1 <= nums.length <= 2 * 10^4
- -10^9 <= nums[i] <= 10^9

*Idea:*

Since our target harmonious array is dealing with the absolute value of its elements and since it's a subsequence of our numbers array (**N**), we don't need to worry about the order of numbers or their index in **N**.

If all we care about is *what* numbers appear in **N** and not their order or index, then it means that we should start by building a **frequency map** from **N**.

Then we can just iterate through the entries in our frequency map (**fmap**) and keep track of the largest value found by adding each number's (**key**) frequency (**val**) with the frequency of **key+1**.

We should then **return** the best result (**ans**).

*Implementation:*

Since javascript's **Map()** stores its keys as strings, you need to use some method of converting the key back into a number before adding **1**. The normal way to do this is with **parseInt()**, but applying a double **bitwise NOT** (**~**) does the same thing far more efficiently, as long as the number is greater than **-2^31** and less than **2^31**.

**Javascript Code:**

```
var findLHS = function(N) {
let fmap = new Map(), ans = 0
for (let num of N)
fmap.set(num, (fmap.get(num) || 0) + 1)
for (let [key,val] of fmap)
if (fmap.has(~~key+1))
ans = Math.max(ans, val + fmap.get(~~key+1))
return ans
};
```

## Top comments (0)