Super Ugly Number: Multi-Pointer DP with Custom Primes

313. Super Ugly Number gives you an array of primes and an integer n. Your job is to return the nth super ugly number, where a super ugly number is a positive integer whose only prime factors come from your given primes array. The number 1 is always considered a super ugly number, so dp[0] is always 1.

For example, with primes = [2, 7, 13, 19], the sequence starts: 1, 2, 4, 7, 8, 13, 14, 19, 26, ... Each of those numbers has only 2, 7, 13, or 19 as prime factors.

The approach: one pointer per prime

The key insight is that every super ugly number is some previous super ugly number multiplied by one of the primes. So if you already know the first i super ugly numbers in sorted order, you can always compute the next one.

Maintain an array dp where dp[i] holds the (i+1)-th super ugly number. Also maintain a pointer array ptrs, one pointer per prime. The pointer ptrs[j] tells you which entry in dp to multiply by primes[j] to get a candidate for the next super ugly number.

At each step:

• Compute candidates[j] = dp[ptrs[j]] * primes[j] for every prime.
• Set dp[i] = min(candidates).
• Advance every pointer j where candidates[j] == dp[i]. Advancing all tied pointers in one shot is what prevents duplicates. If dp[ptrs[j]] * primes[j] equals the chosen minimum for two different primes, both would otherwise generate the same number again on the next step.

This is a generalization of the classic two-pointer merge: instead of merging two sorted sequences, you are merging k implicit sorted sequences simultaneously (one per prime). Each sequence is [1*p, 2*p, 4*p, 7*p, ...] where the multipliers are previous super ugly numbers.

def nthSuperUglyNumber(n: int, primes: list[int]) -> int:
    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[n - 1]

Complexity

Where k is the number of primes. The outer loop runs n - 1 times, and each iteration computes k candidates and scans all k pointers to advance ties. Space is O(n) for the dp array and O(k) for the pointers.

The building blocks

This problem is built from two reusable patterns.

Multi-pointer merge. You are generating k implicit sorted lists and always picking the global minimum across them. The same idea powers Merge K Sorted Lists, which uses a heap to track k list heads. Here, instead of a heap, you keep k integer pointers, which works because the dp array is already sorted as you build it.

DP with implicit sorted generation. Each dp[i] depends only on previously computed dp values, so you can fill the array in one pass from left to right. The Ugly Number II problem (LeetCode 264) is a special case of this exact same approach using only the primes 2, 3, and 5.

Edge cases

• n = 1: The loop body never runs, and you return dp[0] = 1. Correct, since 1 is always the first super ugly number.
• primes = [2]: The sequence degenerates to powers of 2 (1, 2, 4, 8, 16, ...). The single pointer just advances every step with no ties.
• Large n: With n up to 100,000 and up to 100 primes (per LeetCode constraints), the O(n * k) cost is around 10 million operations, which is well within time limits.

From understanding to recall

Following the walkthrough above, the logic probably feels clear. But the tricky part in an interview is getting the deduplication right without thinking about it. Why do you advance all tied pointers at once? What goes wrong if you advance only one?

If you advance only the first tied pointer, the other prime will generate the same number again next step, and you will insert a duplicate into dp. The whole solution depends on that one detail being automatic.

Spaced repetition makes it automatic. You write the solution from scratch at increasing intervals, focusing on that exact deduplication step each time. After a few reps, your hand writes if candidates[j] == dp[i]: ptrs[j] += 1 inside the loop without your brain having to reconstruct the reasoning.

Related posts

• Merge K Sorted Lists - The heap-based version of n-way merge, same core pattern with a different data structure
• Perfect Squares - Another DP problem where each state is the minimum across multiple backward jumps
• Coin Change - The foundational unbounded knapsack DP that shares the same "try all options, pick the minimum" structure