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.

Longest Harmonious Subsequence — LeetCode 594 Python Solution

EasyArrayHash TableCountingSortingSliding Window

Problem: #594
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

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

Python

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

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the array \textit{nums} auxiliary

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.

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.