Problem 594

Abstract / Summary

Find the longest subsequence with two different values differing by one.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
13 lines | 340 bytes | submitted September 19, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 65% (600k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Counting
  • Hash Table
  • Sliding Window
  • Sorting
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.73 | σ = 1.09

Complexity Analysis

Time: loglinear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
40 links | 26 authors | 9 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

1 easy 6 medium 2 hard
10 solutions   September 19, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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