An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
Example 1:
Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
Example 2:
Input: n = 1 Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Constraints:
1 <= n <= 1690Problem 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.
The idea is to use an array to store the ugly numbers and use three pointers for 2, 3, and 5 to calculate the next potential ugly numbers. We then choose the minimum of these numbers to be the next ugly number and appropriately move the pointers.
The code defines a function nthUglyNumber that employs dynamic programming with three pointers to generate ugly numbers in sequence and return the nth ugly number. We use an auxiliary array ugly to store ugly numbers, and we maintain pointers i2, i3, and i5 to track the current position of multiplication for 2, 3, and 5 respectively. The next_2, next_3, and next_5 variables hold the next potential candidates for ugly numbers, and we compute the next ugly number as the minimum of these three values.
Time Complexity: O(n), where n is the number of ugly numbers to generate.
Space Complexity: O(n), for storing the ugly numbers array.
This method involves using a min-heap to manage the sequence of potential ugly numbers. We start with 1 in the min-heap and repeatedly extract the smallest element, multiplying it by 2, 3, and 5 to generate new candidates, which are then inserted back into the heap. Duplicate entries are avoided by using a set for tracking which numbers have been added to the heap.
The solution uses a min-heap to keep track of and retrieve the smallest ugly number, avoiding duplicates by using a set. It generates ugly numbers by multiplying the current smallest number by 2, 3, and 5, inserting valid new numbers back into the heap.
Time Complexity: O(n log n), primarily due to heap operations.
Space Complexity: O(n), for data structures that might store up to n numbers.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Three Pointers | Time Complexity: |
| Min-Heap Approach | Time Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Three Pointers | O(n) | O(n) | Best choice for interviews and large n; avoids heap overhead while generating numbers in sorted order |
| Min-Heap with Hash Set | O(n log n) | O(n) | Useful when modeling the problem as ordered generation using a priority queue |
Ugly Number II | Simple Explanation | Dry Run | codestorywithMIK • codestorywithMIK • 27,453 views views
Watch 9 more video solutions →Practice Ugly Number II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor