Skip to main content
Talentd

Ugly Number II - Solution & Explanation

MediumHash TableMathDynamic ProgrammingHeap (Priority Queue)13 min readAsked at: Amazon, Microsoft, Goldman Sachs +6
Practice this problem

Problem Statement

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 <= 1690

Approach Overview

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.

Approach 1: Dynamic Programming with Three Pointers

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of ugly numbers to generate.
Space Complexity: O(n), for storing the ugly numbers array.

Try this approach in the editor →

Approach 2: Min-Heap Approach

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.

Code

C++Python

C++

Python

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScriptC#

Python

Java

C++

Go

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Three Pointers

Time Complexity: O(n), where n is the number of ugly numbers to generate.
Space Complexity: O(n), for storing the ugly numbers array.

Min-Heap Approach

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Three PointersO(n)O(n)Best choice for interviews and large n; avoids heap overhead while generating numbers in sorted order
Min-Heap with Hash SetO(n log n)O(n)Useful when modeling the problem as ordered generation using a priority queue

Video Solution

Ugly Number II | Simple Explanation | Dry Run | codestorywithMIK • codestorywithMIK • 30,682 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Ugly Number II easy or hard?
Ugly Number II is generally rated as a medium difficulty problem. The brute-force idea is simple, but identifying the optimized three-pointer dynamic programming pattern requires deeper understanding of sequence generation and duplicate handling.
How to solve Ugly Number II in O(n)?
Use a dynamic programming array where dp[i] stores the ith ugly number. Track three indices for multiples of 2, 3, and 5, compute the next candidate values, and pick the smallest each iteration. Increment the pointer(s) that produced the chosen value to avoid duplicates.
What is the best approach for Ugly Number II?
The most efficient solution uses dynamic programming with three pointers. Maintain pointers for multiples of 2, 3, and 5 and generate the sequence iteratively while keeping it sorted. This approach runs in O(n) time and O(n) space and avoids duplicate values.
What data structure is used in Ugly Number II?
The optimal solution primarily uses an array for dynamic programming and three index pointers. An alternative implementation uses a min-heap (priority queue) combined with a hash set to maintain order and prevent duplicate values.
What is the time complexity of Ugly Number II?
The optimal dynamic programming approach runs in O(n) time because each ugly number is generated once using three pointer comparisons. Space complexity is O(n) to store the sequence. A heap-based approach takes O(n log n) time due to priority queue operations.
Ugly Number II Python or Java solution approach?
Both Python and Java implementations typically use the three-pointer dynamic programming technique. Maintain an array of size n, compute candidates from the current pointers, and update the pointers whenever their multiple is selected. This keeps the sequence sorted and efficient.
Is Ugly Number II asked at Google, Amazon, or Meta?
Ugly Number II appears in interview preparation lists for companies such as Amazon, Google, and Microsoft. The problem tests dynamic programming fundamentals, sequence generation, and pointer optimization techniques.

Ready to solve this problem?

Practice Ugly Number II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Primes

Next

Merge k Sorted Lists