Python 0264.py
class Solution:
def nthUglyNumber(self, n: int) -> int:
next = [ 1 ]
for _ in range(n - 1):
current = heappop(next)
while next and next[0] == current:
heappop(next)
heappush(next, current * 2)
heappush(next, current * 3)
heappush(next, current * 5)
return next[0]
Difficulty
and has an acceptance rate of about 50% (1+ million submissions).
Typical patterns to solve this problem:
- Dynamic Programming
- Hash Table
- Heap (Priority Queue)
- Math
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 computes the n-th ugly number-an integer whose prime factors are limited to 2, 3, and 5. It employs a min-heap to generate ugly numbers in ascending order while automatically discarding duplicates. The algorithm proceeds by repeatedly extracting the smallest candidate, expanding it with the allowed multipliers, and maintaining the heap invariant.
Initialization
next = [1]
A list containing the first ugly number, 1, is created and will serve as the underlying container for the heap. By initializing the heap with a single element, the algorithm guarantees a valid starting point for subsequent extraction and insertion operations.
Main Generation Loop
for _ in range(n - 1):
current = heappop(next)
# duplicate removal and insertion follow
The loop iterates exactly n - 1 times because the first ugly number is already present. In each iteration the smallest element is removed from the heap, representing the next ugly number in the ordered sequence.
Duplicate Elimination
while next and next[0] == current:
heappop(next)
After extracting the current smallest value, the code checks whether the next element in the heap equals the same value. If so, it continues popping until the top of the heap differs. This construct ensures that repeated values-arising from different multiplication paths-are not processed multiple times, thereby preserving uniqueness in the generated sequence.
Insertion of New Candidates
heappush(next, current * 2)
heappush(next, current * 3)
heappush(next, current * 5)
The three allowed prime factors are applied to the extracted ugly number, and the resulting products are inserted back into the heap. Because the heap maintains a sorted order, these new candidates will be considered in proper ascending order during future iterations.
Edge Cases Handled
When the input n equals 1, the loop body is never executed because the range evaluates to zero iterations. The function then directly returns next[0], which is the initial value 1, correctly handling the smallest possible request. The duplicate elimination step also implicitly handles cases where multiple generation paths converge on the same number-for example, 6 can be produced as 2 × 3 or 3 × 2. By removing subsequent identical entries, the algorithm avoids counting such numbers twice.
Performance Optimizations
The use of a min-heap provides an efficient mechanism for always retrieving the smallest pending ugly number without scanning the entire collection. By pushing only the three direct multiples of each extracted value, the algorithm limits the growth of the heap to a manageable size, avoiding the explosion that would occur if all possible combinations were generated indiscriminately. The duplicate removal loop prevents the heap from accumulating redundant entries, which reduces both the number of heap operations and the memory footprint. Together, these choices keep the execution focused on the essential candidates needed to reach the n-th ugly number.
ELI5 - Simplified Explanation
Imagine a magical basket that starts with the number one inside. This basket is very special because it likes to grow by playing with the numbers two, three, and five. To find the next number in line, the basket looks at the smallest number currently sitting inside. It takes that tiny number out and creates three new versions of it by multiplying it by two, three, and five. These new results are tossed back into the basket to grow even more later. Because the basket might end up with the same number a few different times, it carefully checks to make sure no duplicates are sitting around. This process happens over and over again like a repeating game. Every time the basket repeats this step, a new number gets generated until reaching the specific spot being searched for. The basket keeps the smallest results organized so that the right number always pops out at the end.
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++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | JS | Java | C# | Go | ||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| MemoryLimitExceeded | C++ | Python | ||||||||
| Progiez | C++ | Python | Java | |||||||
| github | aylei | Rust | ||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| chenyanzhe | C++ | |||||||||
| everthis | JS | |||||||||
| fengvyi | C++ | |||||||||
| fpdjsns | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| lennylxx | C | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| MacJim | C++ | |||||||||
| qiyuangong | Python | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| vli02 | C | |||||||||
| wisdompeak | C++ | |||||||||
| zfang399 | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, Python | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||
| Progiez | C++, Java, Python | |||||||||
| aylei | Rust | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| chenyanzhe | C++ | |||||||||
| everthis | JavaScript | |||||||||
| fengvyi | C++ | |||||||||
| fpdjsns | C++ | |||||||||
| halfrost | Go | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| lennylxx | C | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| MacJim | C++ | |||||||||
| qiyuangong | Python | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| vli02 | C | |||||||||
| wisdompeak | C++ | |||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 263: Ugly Number
- problem 279: Perfect Squares
- problem 313: Super Ugly Number
- problem 1201: Ugly Number III
Solved On The Same Day
- problem 263: Ugly Number
- problem 461: Hamming Distance
- problem 133: Clone Graph
- problem 142: Linked List Cycle II
- problem 143: Reorder List
- problem 313: Super Ugly Number
- problem 454: 4Sum II
- problem 477: Total Hamming Distance
- problem 10: Regular Expression Matching
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