Python 0594.py
class Solution:
def findLHS(self, nums: List[int]) -> int:
freq = defaultdict(int)
for n in nums:
freq[n] += 1
best = 0
for f in sorted(freq):
if f+1 in freq:
current = freq[f] + freq[f+1]
best = max(best, current)
return best
Difficulty
and has an acceptance rate of about 65% (600k+ submissions).
Typical patterns to solve this problem:
- Array
- Counting
- Hash Table
- Sliding Window
- Sorting
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation solves the problem of finding the length of the longest harmonious subsequence (LHS) in an integer array. A harmonious subsequence is defined as a subsequence where the difference between its maximum and minimum values is exactly one. The algorithm builds a frequency map of the input values, iterates over the distinct numbers in sorted order, and aggregates counts of numbers that are consecutive. The maximum aggregated count encountered is returned as the answer.
Key Steps
Frequency Counting
The first phase constructs a histogram of the input values. By using a defaultdict with an integer default, each occurrence of a number increments its count in constant time.
freq = defaultdict(int)
for n in nums:
freq[n] += 1
Sorting Distinct Values
To examine only pairs of values that differ by one, the distinct keys of the frequency map are sorted. This ordering guarantees that when a key f is processed, any potential partner f+1 will be positioned immediately after it in the sorted sequence.
for f in sorted(freq):
...
Evaluating Adjacent Values
For each sorted key, the algorithm checks whether the next integer (f+1) exists in the frequency map. If it does, the combined frequency of the two numbers represents the length of a harmonious subsequence that uses all occurrences of both values. The current best length is updated with the larger of the previous best and this combined count.
if f+1 in freq:
current = freq[f] + freq[f+1]
best = max(best, current)
Returning the Result
After the loop finishes, the variable best holds the length of the longest harmonious subsequence found, or zero if no such pair exists. The function returns this value directly.
return best
Edge Cases Handled
The algorithm gracefully handles an empty input array because the frequency map remains empty, the sorting step yields no iteration, and the initial best value of zero is returned. When the array contains a single element, the check for a neighboring value fails, leaving best unchanged at zero, which correctly indicates that no harmonious subsequence exists. If all elements are identical, the sorted keys contain only one entry, the adjacency test fails, and the result is zero, reflecting the absence of a required difference of one. The code also works with negative numbers because the sorting and adjacency check are based on integer arithmetic without any assumptions about sign. Non-consecutive values are ignored because the if f+1 in freq guard ensures that only pairs with the exact required difference contribute to the result.
Performance Optimizations
The use of defaultdict(int) eliminates the need for explicit existence checks before incrementing counts, reducing overhead in the frequency-building loop. Sorting is performed once on the distinct keys rather than on the entire input array, which limits the amount of data processed in the ordering step. The adjacency check accesses the frequency map in constant time, avoiding nested iteration over all pairs of distinct values. Updating the best length with the built-in max function leverages a highly optimized native operation. Collectively, these choices keep the core work linear in the number of input elements plus the cost of sorting the unique values, while avoiding unnecessary data structures or repeated scans.
ELI5 - Simplified Explanation
Imagine you have a big bucket full of numbered building blocks. The goal is to make the longest possible tower by picking two numbers that are right next to each other, like a two and a three.
First, the code goes through your bucket and counts exactly how many of each number you have. It puts these counts into a handy list where it can look them up later. It is just like counting how many red pieces and how many blue pieces are in a pile.
After everything is counted, the code starts looking for pairs of numbers that are neighbors. It checks every number to see if there is another number just one step higher in the bucket. If it finds a pair, like a one and a two, it adds up how many of those blocks there are in total.
As it looks through the numbers, it keeps a secret note of which pair creates the tallest tower seen so far. It keeps comparing the new towers it finds to that secret note. If a new pair makes a tower that is even bigger, it updates the note so that the biggest tower is always remembered. By the time it finishes checking all the numbers, it has found the tallest tower possible.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Java | Python | TS | |||||
| WalkCCC | C++ | Java | Python | |||||||
| leetcode.ca | C++ | Java | Python | Rust | Go | TS | ||||
| LeetcodeHelp | C++ | Java | Python | |||||||
| Progiez | C++ | Java | Python | |||||||
| github | BigEggStudy | C# | ||||||||
| black-shadows | C++ | |||||||||
| chandansgowda | Python | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fpdjsns | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| Krazune | Java | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| lzl124631x | C++ | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| vthwang | Java | |||||||||
| wisdompeak | C++ | |||||||||
| YuriSpiridonov | Python | |||||||||
| zfang399 | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| chandansgowda | Python | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fpdjsns | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| Krazune | Java | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| lzl124631x | C++ | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| vthwang | Java | |||||||||
| wisdompeak | C++ | |||||||||
| YuriSpiridonov | Python | |||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 566: Reshape the Matrix
- problem 324: Wiggle Sort II
- problem 386: Lexicographical Numbers
- problem 388: Longest Absolute File Path
- problem 390: Elimination Game
- problem 406: Queue Reconstruction by Height
- problem 491: Non-decreasing Subsequences
- problem 410: Split Array Largest Sum
- problem 472: Concatenated Words
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality