Ugly Number II
Medium · Heap / Priority Queue · Explanation and code example
Three Monotone Candidate Streams
How it works
Every ugly number after one is an earlier ugly number multiplied by two, three, or five. Keep one index for each stream and append the smallest next candidate. Advance every stream that produced that candidate so duplicates are generated only once.
Steps
- Start the sequence at one.
- Compute the next multiples from the three indices.
- Append the minimum and advance all matching indices until n values exist.
Complexity
- Time: O(n).
- Space: O(n).
Things to watch for
- Use separate if checks rather than elif when candidates tie.
- One is the first ugly number.
- Advancing only one tied stream creates duplicates.
Python code example
class Solution:
def nthUglyNumber(self, n: int) -> int:
nums = [1]
i2 = 0
i3 = 0
i5 = 0
while len(nums) < n:
next2 = nums[i2] * 2
next3 = nums[i3] * 3
next5 = nums[i5] * 5
next = min(next2, next3, next5)
if next == next2:
i2 += 1
if next == next3:
i3 += 1
if next == next5:
i5 += 1
nums.append(next)
return nums[-1]
C++ code example
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> uglyNums{1};
int i2 = 0;
int i3 = 0;
int i5 = 0;
while (uglyNums.size() < n) {
const long long next2 = 2LL * uglyNums[i2];
const long long next3 = 3LL * uglyNums[i3];
const long long next5 = 5LL * uglyNums[i5];
const int next = min({next2, next3, next5});
if (next == next2)
++i2;
if (next == next3)
++i3;
if (next == next5)
++i5;
uglyNums.push_back(next);
}
return uglyNums.back();
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.