K-way Merge — Ugly Number II
↗ LeetCode: Ugly Number II · Medium · pattern chapter →
An ugly number has only 2, 3, or 5 as prime factors. 1 is ugly by convention. Return the n-th ugly number.
Example 1 — n = 10 → 12 (sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12) Example 2 — n = 1 → 1Example 3 — n = 11 → 15
Constraints — 1 ≤ n ≤ 1690. Brute checks every integer for 2/3/5-only factorisation — O(N·log N) where N = the 1690th ugly number ≈ 2·10⁹ (dies past 1 min). Three-pointer merge from {2,3,5} is O(n) = 10³ ops = <1 microsec, scales to 10⁶ queries/sec.
Interview timer00:00
Approach 1 — Test each candidate
Intuition. For each integer, divide by 2, 3, 5 repeatedly; if it reduces to 1, it's ugly.
Complexity — Time up to O(n · answer log answer) — too slow.
Approach 2 — Min-heap merge of 3 streams
Insight. Every ugly number u > 1 is 2·u' or 3·u' or 5·u' where u' is a smaller ugly number. So the sequence is the sorted merge of three streams: {2·u_i}, {3·u_i}, {5·u_i}.
- Push
1into heap; track seen set for dedup. - Pop
x(n-th pop = answer). Push2x, 3x, 5xif unseen.
int nthUglyNumberHeap(int n) {
PriorityQueue<Long> pq = new PriorityQueue<>();
Set<Long> seen = new HashSet<>();
pq.offer(1L); seen.add(1L);
long ans = 1;
int[] primes = {2, 3, 5};
for (int i = 0; i < n; i++) {
ans = pq.poll();
for (int p : primes) {
long next = ans * p;
if (seen.add(next)) pq.offer(next);
}
}
return (int) ans;
}Complexity — Time O(n log n); Space O(n).
Approach 3 — Three pointers (canonical O(n))
Insight from heap. Instead of a heap + seen set, maintain three indices i2, i3, i5 into the growing ugly array. Next ugly = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5). Advance whichever pointer(s) produced the minimum — all of them if tied — to skip duplicates.
int nthUglyNumber(int n) {
int[] ugly = new int[n];
ugly[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < n; i++) {
int next2 = ugly[i2] * 2, next3 = ugly[i3] * 3, next5 = ugly[i5] * 5;
int next = Math.min(next2, Math.min(next3, next5));
ugly[i] = next;
if (next == next2) i2++;
if (next == next3) i3++;
if (next == next5) i5++;
}
return ugly[n - 1];
}Complexity — Time O(n); Space O(n) for the array.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Test each integer | very slow | O(1) | baseline |
| Min-heap merge | O(n log n) | O(n) | correct, uses heap pattern |
| Three-pointer merge | O(n) | O(n) | canonical answer |
When to use which
- Standard → three-pointer merge.
- "With k primes, not just {2,3,5}" → generalize to k pointers; O(nk).
- "Super ugly numbers" → same, with
primes[]given; min-heap gets simpler than k pointers. - "nth prime" or "smallest k of type X" → same merge template if
xis a closed set.
Related problems
- Super Ugly Number — k-primes generalization
- Merge k Sorted Lists — the pattern seed
- Perfect Squares — DP alternative