Super Ugly Number — Multi-Pointer Heap DP Interview

Problem Statement#

A super ugly number has all its prime factors in the array primes. Return the nth super ugly number, where the sequence is sorted in ascending order starting at 1.

Constraints:

• 1 <= n <= 10^5
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] is guaranteed to be prime.

Input:  n = 12, primes = [2,7,13,19]
Output: 32

Input:  n = 1, primes = [2,3,5]
Output: 1

Why This Problem Matters#

LeetCode 313 generalizes the classic Ugly Number II to K primes. It appears in Amazon, Google, and Microsoft interviews because it tests two distinct heap mastery skills: deduplication of generated values and amortized pointer DP.

This priority queue interview problem teaches a pattern that powers number-theoretic sequence generation, B-smooth number enumeration, and even some music-theory algorithms.

The Core Insight#

Use a min-heap of candidates (value, prime, source_index). Each pop gives the next ugly number; multiply by every prime to seed new candidates. Use a set to dedupe. Faster: K-pointer DP where dp[i] is the i-th ugly number and each prime has a pointer into dp; advance the pointers whose product equals the new minimum.

Visual Dry Run#

primes = [2, 7, 13, 19], dp DP version

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        # K-pointer DP: O(n * k) time, O(n + k) space
        dp = [1] * n
        ptrs = [0] * len(primes)
        for i in range(1, n):
            candidates = [dp[ptrs[j]] * primes[j] for j in range(len(primes))]
            dp[i] = min(candidates)
            for j in range(len(primes)):
                if candidates[j] == dp[i]:
                    ptrs[j] += 1
        return dp[-1]
 
    def nthSuperUglyNumberHeap(self, n: int, primes: List[int]) -> int:
        # Heap version: O(n * k * log(n*k))
        heap = [1]
        seen = {1}
        for _ in range(n):
            cur = heapq.heappop(heap)
            for p in primes:
                nxt = cur * p
                if nxt not in seen:
                    seen.add(nxt)
                    heapq.heappush(heap, nxt)
        return cur

var nthSuperUglyNumber = function(n, primes) {
    const dp = new Array(n).fill(1);
    const ptrs = new Array(primes.length).fill(0);
    for (let i = 1; i < n; i++) {
        let mn = Infinity;
        for (let j = 0; j < primes.length; j++) {
            const cand = dp[ptrs[j]] * primes[j];
            if (cand < mn) mn = cand;
        }
        dp[i] = mn;
        for (let j = 0; j < primes.length; j++) {
            if (dp[ptrs[j]] * primes[j] === mn) ptrs[j]++;
        }
    }
    return dp[n - 1];
};
 
// Heap variant for completeness
class MinHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i] < this.h[p]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l] < this.h[m]) m = l;
            if (r < n && this.h[r] < this.h[m]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}

Time: O(n * k) — DP version. Heap version is O(n * k * log(nk)). Space: O(n + k) — DP array plus pointers.

Common Mistakes#

• Forgetting the dedup if candidates[j] == dp[i] — you must advance every prime that produced the min, not just one.
• Using a set with the heap incurs O(nk) memory; the DP version is leaner.
• Off-by-one: dp[0] must be 1.
• Ignoring overflow when primes are near 1000 and n near 10^5 — use BigInt in JS for safety in some variants.
• Pushing duplicates into the heap and not deduping — explodes memory.

Interview Tips#

• Show both approaches: heap is intuitive, DP is faster for this constraint.
• Walk through the pointer-advance step on a small example.
• Connect this to the classic 3-pointer Ugly Number II as the K=3 case.
• Mention that primes do not have to be primes mathematically — only relatively coprime is enough; the algorithm still works.

Follow-up Questions#

• Can you do better than O(nk)? Hint: use a heap of (next_value, prime, pointer) for O(n log k).
• What if n is 10^9 and k is 100? Hint: log-space sieving.
• Generalize to "all factors from set S" — non-prime S. Hint: same algorithm, no factorization assumed.
• Stream the sequence forever. Hint: heap version handles unbounded n.
• Find the kth super ugly number modulo p. Hint: same algorithm; apply mod at output.

Key Takeaways#

• LeetCode 313 Super Ugly Number generalizes Ugly Number II to K primes.
• DP with K pointers runs in O(n*k) time and O(n+k) space.
• Heap version runs in O(n * k * log(nk)) and is easier to write but slower.
• Always advance every pointer whose candidate equals the new minimum to avoid duplicates.
• The first ugly number is 1 — dp[0] = 1.
• This priority queue interview problem teaches a reusable sequence-generation pattern.
• Common at Amazon and Google heap FAANG interview rounds.