EasyNo. 0594

Longest Harmonious Subsequence — LeetCode 594 Python Solution

Topics
Array, Hash Table, Counting, Sorting, Sliding Window
Reading time
2 min

The problem

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.

Python solution

PythonSolution
class Solution:
    def findLHS(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)

Complexity

Time
O(n)
Space · auxiliary
O(n)where n is the length of the array nums

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 594. Longest Harmonious Subsequence is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0169Majority ElementEasy
0229Majority Element IIMedium
0347Top K Frequent ElementsMedium
0621Task SchedulerMedium
0632Smallest Range Covering Elements from K ListsHard
0692Top K Frequent WordsMedium

Frequently asked questions

How hard is LeetCode 594. Longest Harmonious Subsequence?

LeetCode 594. Longest Harmonious Subsequence is rated Easy on LeetCode.

What is the time complexity of LeetCode 594. Longest Harmonious Subsequence?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 594. Longest Harmonious Subsequence?

The Python solution on this page uses O(n), where n is the length of the array \textit{nums} auxiliary space.

What topics does LeetCode 594. Longest Harmonious Subsequence cover?

LeetCode 594. Longest Harmonious Subsequence is tagged Array, Hash Table, Counting, Sorting and Sliding Window on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.