Ugly Number II — Min-Heap or Three-Pointer DP

Problem Statement#

An ugly number has only 2, 3, and 5 as prime factors. Given an integer n, return the n-th ugly number. The sequence starts at 1.

Constraints:

• 1 <= n <= 1690

Input:  n = 10
Output: 12

Input:  n = 1
Output: 1

Why This Problem Matters#

Ugly Number II shows up at Google and Amazon when interviewers want to test multi-way merge intuition. It is the smallest "k-streams in lockstep" problem and the perfect setup for Super Ugly Number, Smallest Range, and offline event scheduling.

It also illustrates a key idea: when the same element can be produced by several generators, you must dedupe — either with a visited set on the heap, or by structurally avoiding duplicates with disciplined pointers.

The Core Insight#

Every ugly number is derivable as 2x, 3y, or 5*z for some earlier ugly numbers x, y, z. Two clean approaches:

1. Min-heap — start with 1, pop the smallest, push 2x, 3x, 5x, dedupe with a set.
2. DP with three pointers i2, i3, i5 — at each step take the minimum of dp[i2]*2, dp[i3]*3, dp[i5]*5 and advance every pointer that produced the min (this dedupes structurally).

DP is faster and uses less memory; the heap is more general (extends to k primes).

Visual Dry Run#

DP build for n = 10:

Solution (Optimal)#

import heapq
 
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # DP three-pointer (fastest)
        dp = [1] * n
        i2 = i3 = i5 = 0
        for k in range(1, n):
            nxt = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
            dp[k] = nxt
            if nxt == dp[i2] * 2: i2 += 1
            if nxt == dp[i3] * 3: i3 += 1
            if nxt == dp[i5] * 5: i5 += 1
        return dp[n - 1]
 
    def nthUglyNumberHeap(self, n: int) -> int:
        seen, heap = {1}, [1]
        for _ in range(n - 1):
            x = heapq.heappop(heap)
            for p in (2, 3, 5):
                if x * p not in seen:
                    seen.add(x * p)
                    heapq.heappush(heap, x * p)
        return heap[0]

var nthUglyNumber = function(n) {
    const dp = new Array(n).fill(1);
    let i2 = 0, i3 = 0, i5 = 0;
    for (let k = 1; k < n; k++) {
        const nxt = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5);
        dp[k] = nxt;
        if (nxt === dp[i2] * 2) i2++;
        if (nxt === dp[i3] * 3) i3++;
        if (nxt === dp[i5] * 5) i5++;
    }
    return dp[n - 1];
};

Time: DP O(n) — single pass, three pointer increments. Heap O(n log n). Space: O(n) for the dp array; O(n) for the heap and seen set.

Common Mistakes#

• Using if/elif/else on the three pointer comparisons — fails to advance multiple pointers when sums tie (causes duplicates)
• Forgetting the visited set in the heap version — same value gets pushed multiple times
• Treating 1 as not ugly — it is
• Confusing "ugly" with "happy" — different problem
• Off-by-one on the n-th element — 1 is the first ugly number, so dp[n-1]

Interview Tips#

• Lead with the heap solution (intuitive), then offer DP for O(n)
• Explain the duplicate trap — if/if/if not if/elif/else — interviewers love that catch
• Mention scale: only 1690 ugly numbers fit in a 32-bit signed int
• Generalize: Super Ugly Number replaces 2,3,5 with k primes — heap version still works

Follow-up Questions#

• Replace 2,3,5 with k arbitrary primes? See LeetCode 313 — heap pattern with k pointers
• What if n is huge (10^9)? Pre-build a logarithm-based estimate, not feasible in pure Python
• Find the n-th product of two sets? Same template, different generators
• Streaming version where new primes can appear? Heap with dynamic source list
• Is dp[i] * p ever non-monotonic? No — pointers only move forward

Key Takeaways#

• Two equivalent strategies: min-heap with dedupe, or three-pointer DP
• DP runs in O(n), heap in O(n log n)
• Use independent ifs on the three pointers — never elif — to dedupe ties structurally
• 1 is the first ugly number; the sequence has 1690 entries within 32-bit ints
• Same multi-source merge pattern extends to Super Ugly Number and k-pair sums
• Heap version is more general; DP is faster when the prime set is fixed
• Memorize both — Google and Amazon priority queue interview material