Super Ugly Number - Video Solutions

Problem Overview: You need the nth super ugly number. A super ugly number is a positive integer whose prime factors belong only to a given list primes. The sequence starts from 1. The task is essentially generating numbers in sorted order while restricting their prime factors.

Approach 1: Dynamic Programming Using Merge List (O(n * k) time, O(n + k) space)

This approach builds the sequence incrementally using dynamic programming. Maintain an array dp where dp[i] stores the i-th super ugly number. For each prime in primes, track an index pointing to the position in dp whose value should be multiplied by that prime next. At each step, compute candidates like dp[index[j]] * primes[j], pick the minimum, and append it to the sequence. If multiple primes generate the same value, increment all corresponding indices to avoid duplicates. This works like merging k sorted lists of multiples and guarantees the numbers remain sorted.

Approach 2: Heap-Based Approach (O(n log k) time, O(n + k) space)

A min-heap keeps track of the next candidate numbers generated from each prime. Start with 1 in the result list. Push tuples representing the next value for each prime into a heap. Each heap element stores the value, the prime, and the index in the generated sequence. Pop the smallest value, append it to the result if it is new, then push the next multiple for that prime using the next index. The heap always exposes the smallest candidate, so the sequence remains sorted. This method resembles merging sorted streams and works well when the number of primes is large.

The problem mixes ideas from math and sequence generation. The key challenge is preventing duplicates while keeping numbers sorted without generating all integers and factorizing them.

Recommended for interviews: The dynamic programming merge-list method is the expected solution. It runs in O(n * k) time and avoids heap overhead while clearly demonstrating how multiple sorted sequences are merged. Explaining the pointer updates and duplicate handling shows strong understanding. The heap approach is also valid and often easier to implement conceptually, but interviewers typically prefer the DP pointer technique for its deterministic behavior and lower constant factors.