264. Ugly Number II Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n^th 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.

Python

def nthUglyNumber(n):
    ugly = [0] * n
    ugly[0] = 1
    i2, i3, i5 = 0, 0, 0
    next_2, next_3, next_5 = 2, 3, 5

    for i in range(1, n):
        next_ugly = min(next_2, next_3, next_5)
        ugly[i] = next_ugly

        if next_ugly == next_2:
            i2 += 1
            next_2 = ugly[i2] * 2
        if next_ugly == next_3:
            i3 += 1
            next_3 = ugly[i3] * 3
        if next_ugly == next_5:
            i5 += 1
            next_5 = ugly[i5] * 5

    return ugly[-1]

n = 10
print(nthUglyNumber(n))  # Output: 12

Java

public class Main {

    public static int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        int next_2 = 2, next_3 = 3, next_5 = 5;

        for (int i = 1; i < n; i++) {
            int next_ugly = Math.min(next_2, Math.min(next_3, next_5));
            ugly[i] = next_ugly;

            if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
            if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
            if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
        }
        return ugly[n - 1];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(nthUglyNumber(n)); // Output: 12
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int nthUglyNumber(int n) {
    vector<int> ugly(n);
    ugly[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    int next_2 = 2, next_3 = 3, next_5 = 5;

    for (int i = 1; i < n; ++i) {
        int next_ugly = min(next_2, min(next_3, next_5));
        ugly[i] = next_ugly;

        if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
        if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
        if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
    }
    return ugly[n - 1];
}

int main() {
    int n = 10;
    cout << nthUglyNumber(n) << endl; // Output: 12
    return 0;
}

JavaScript

function nthUglyNumber(n) {
    const ugly = new Array(n);
    ugly[0] = 1;
    let i2 = 0, i3 = 0, i5 = 0;
    let next_2 = 2, next_3 = 3, next_5 = 5;

    for (let i = 1; i < n; i++) {
        const next_ugly = Math.min(next_2, next_3, next_5);
        ugly[i] = next_ugly;

        if (next_ugly === next_2) next_2 = ugly[++i2] * 2;
        if (next_ugly === next_3) next_3 = ugly[++i3] * 3;
        if (next_ugly === next_5) next_5 = ugly[++i5] * 5;
    }
    return ugly[n - 1];
}

const n = 10;
console.log(nthUglyNumber(n)); // Output: 12

#include <stdio.h>

int nthUglyNumber(int n) {
    int ugly[n];
    ugly[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    int next_2 = 2, next_3 = 3, next_5 = 5;

    for (int i = 1; i < n; i++) {
        int next_ugly = next_2 < next_3 ? (next_2 < next_5 ? next_2 : next_5) : (next_3 < next_5 ? next_3 : next_5);
        ugly[i] = next_ugly;

        if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
        if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
        if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
    }
    return ugly[n-1];
}

int main() {
    int n = 10;
    printf("%d\n", nthUglyNumber(n)); // Output: 12
    return 0;
}

using System;

public class Solution {
    public int NthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        int next_2 = 2, next_3 = 3, next_5 = 5;

        for (int i = 1; i < n; i++) {
            int next_ugly = Math.Min(next_2, Math.Min(next_3, next_5));
            ugly[i] = next_ugly;

            if (next_ugly == next_2) next_2 = ugly[++i2] * 2;
            if (next_ugly == next_3) next_3 = ugly[++i3] * 3;
            if (next_ugly == next_5) next_5 = ugly[++i5] * 5;
        }
        return ugly[n - 1];
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int n = 10;
        Console.WriteLine(sol.NthUglyNumber(n)); // Output: 12
    }
}

The Python solution uses a list to store ugly numbers and three indices corresponding to the factors 2, 3, and 5. In each iteration, it calculates the next potential ugly numbers, updates the array, and adjusts the indices accordingly.

Complexity

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

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.

Python

import heapq

def nthUglyNumber(n):
    min_heap = [1]
    seen = {1}

    for _ in range(n):
        curr_ugly = heapq.heappop(min_heap)
        for factor in [2, 3, 5]:
            new_ugly = curr_ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(min_heap, new_ugly)
    return curr_ugly

n = 10
print(nthUglyNumber(n))  # Output: 12

C++

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

int nthUglyNumber(int n) {
    priority_queue<long, vector<long>, greater<long>> minHeap;
    unordered_set<long> seen;
    minHeap.push(1);
    seen.insert(1);
    long currUgly = 1;

    for (int i = 0; i < n; ++i) {
        currUgly = minHeap.top();
        minHeap.pop();
        if (!seen.count(currUgly * 2)) {
            minHeap.push(currUgly * 2);
            seen.insert(currUgly * 2);
        }
        if (!seen.count(currUgly * 3)) {
            minHeap.push(currUgly * 3);
            seen.insert(currUgly * 3);
        }
        if (!seen.count(currUgly * 5)) {
            minHeap.push(currUgly * 5);
            seen.insert(currUgly * 5);
        }
    }
    return (int)currUgly;
}

int main() {
    int n = 10;
    cout << nthUglyNumber(n) << endl; // Output: 12
    return 0;
}

The Python solution leverages a min-heap for ordering ugly numbers. The smallest number is removed in each iteration and multiplied by 2, 3, and 5 to yield potential new ugly numbers. Tracking entries in a set prevents duplicates in the heap.

Complexity

Time Complexity: O(n log n), dominated by heap operations.
Space Complexity: O(n), for storing the numbers in the min-heap and set.

Try this approach in the editor

Approach 3: Default Approach

func nthUglyNumber(n int) int {
	h := IntHeap([]int{1})
	heap.Init(&h)
	ans := 1
	vis := map[int]bool{1: true}
	for n > 0 {
		ans = heap.Pop(&h).(int)
		for _, v := range []int{2, 3, 5} {
			nxt := ans * v
			if !vis[nxt] {
				vis[nxt] = true
				heap.Push(&h, nxt)
			}
		}
		n--
	}
	return ans
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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 list.
Min-Heap Approach	Time Complexity: `O(n log n)`, dominated by heap operations. Space Complexity: `O(n)`, for storing the numbers in the min-heap and set.
Default Approach	–

Complexity analysis

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

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.

Ugly Number II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Three Pointers

Approach 2: Min-Heap Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Ugly Number II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Three Pointers

Approach 2: Min-Heap Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems