Longest Harmonious Subsequence

Find the length of the longest subsequence where the max and min differ by exactly 1.

hash-map counting subsequence arrays

A harmonious subsequence is a subsequence of a list where the difference between the maximum value and the minimum value is exactly 1. In other words, the subsequence must contain only two distinct values that are consecutive integers. You are given a list of integers `nums`. Write a function `find_lhs(nums)` that returns the length of the longest harmonious subsequence. If there is no such subsequence, return 0.

A subsequence is a sequence that can be derived from the list by deleting some or no elements without changing the order of the remaining elements. For this problem, the order of elements does not matter for the length, only the count of chosen values.

Implement the function `find_lhs(nums)` that takes a list of integers and returns an integer.

Constraints

The input list `nums` may be empty, and its length will be between 0 and 10^5. Each element is an integer in the range [-10^9, 10^9]. The expected time complexity is O(n), and the space complexity is O(n).

Example

>>> find_lhs([1,3,2,2,5,2,3,7])
5
>>> find_lhs([1,2,3,4])
2
>>> find_lhs([1,1,1,1])
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Count the frequency of each number using a dictionary.

For each number x, consider the subsequence formed by x and x+1 (or x and x-1) if both exist.

The answer is the maximum of count[x] + count[x+1] over all x where both counts are positive.

If no such pair exists, return 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.