Ugly Number II - Video Solutions

Problem Overview: The task is to return the nth ugly number. An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. The sequence starts with 1, and every next value must be generated from previous ugly numbers using these factors.

Approach 1: Dynamic Programming with Three Pointers (O(n) time, O(n) space)

This approach builds the sequence of ugly numbers incrementally using dynamic programming. Maintain an array dp where dp[i] stores the ith ugly number. Three pointers track which previous ugly number should be multiplied by 2, 3, and 5. At each step, compute the next candidate values 2 * dp[p2], 3 * dp[p3], and 5 * dp[p5], then choose the smallest. If multiple candidates match the minimum, advance all corresponding pointers to avoid duplicates. This guarantees the sequence stays sorted while generating only valid ugly numbers. The algorithm iterates exactly n times, giving O(n) time and O(n) space for the array.

Approach 2: Min-Heap with Deduplication (O(n log n) time, O(n) space)

This method treats the problem as generating numbers in increasing order using a heap (priority queue). Start with 1 in a min-heap and repeatedly extract the smallest value. For each extracted number, multiply it by 2, 3, and 5, then push the results back into the heap. A hash set prevents inserting duplicates such as 6 generated from both 2×3 and 3×2. Because heap push and pop operations take O(log n), generating n numbers results in O(n log n) time complexity and O(n) space. This approach is conceptually straightforward and mirrors techniques used in sequence generation problems involving priority queues.

The heap solution highlights how ordered generation works with mathematical factor constraints. However, it performs extra heap operations compared to the pointer technique.

Recommended for interviews: The dynamic programming three‑pointer method is the expected solution. It generates ugly numbers in sorted order without expensive heap operations and runs in optimal O(n) time. Interviewers often accept the heap approach first because it shows correct reasoning about ordered generation, but the pointer-based dynamic programming solution demonstrates stronger algorithmic optimization.