LeetCode 264 - Ugly Number II

Difficulty: 🟡 Medium
Topics: Hash Table, Math, Dynamic Programming, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to generate the sequence of ugly numbers and return the nth value in that sequence.

An ugly number is defined as a positive integer whose only prime factors are 2, 3, and 5. This means every ugly number can be formed by multiplying previous ugly numbers by one of these three primes. The sequence begins with 1, which is considered an ugly number by definition.

For example:

6 is ugly because 6 = 2 × 3
8 is ugly because 8 = 2 × 2 × 2
14 is not ugly because it contains the prime factor 7

The input is a single integer n, representing the position in the ugly number sequence. The output is the nth ugly number in ascending order.

The constraint 1 <= n <= 1690 is important. It tells us the sequence size is relatively small, which means precomputing or dynamic programming approaches are completely feasible. However, a naive brute-force method that repeatedly checks every integer for ugliness can still become unnecessarily slow.

There are several edge cases worth recognizing immediately:

n = 1 should return 1
Duplicate values can appear during generation, such as:
6 = 2 × 3
6 = 3 × 2
The generated sequence must remain strictly increasing
We must avoid missing ugly numbers or inserting duplicates

The core challenge is generating ugly numbers efficiently and in sorted order.

Approaches

Brute Force Approach

A straightforward solution is to iterate through positive integers one by one and determine whether each number is ugly.

To check if a number is ugly, we repeatedly divide it by 2, 3, and 5 while possible. If the final result becomes 1, then the number contains no other prime factors and is therefore ugly.

For example:

30
divide by 2 → 15
divide by 3 → 5
divide by 5 → 1
therefore ugly

We continue counting ugly numbers until we reach the nth one.

This approach is correct because every number is explicitly verified. However, it is inefficient because we examine many non-ugly numbers. As n grows, the amount of wasted work becomes significant.

Optimal Dynamic Programming Approach

The key insight is that every ugly number is generated from a previous ugly number by multiplying by 2, 3, or 5.

Instead of checking every integer, we directly build the sequence in sorted order.

Suppose we already know the ugly numbers:

1, 2, 3, 4, 5

The next ugly number must be one of:

previous ugly number × 2
previous ugly number × 3
previous ugly number × 5

We maintain three pointers:

one for the next multiple of 2
one for the next multiple of 3
one for the next multiple of 5

At every step:

compute the next candidates
choose the minimum
append it to the sequence
advance any pointer that produced the chosen value

This guarantees sorted order and avoids duplicates efficiently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k) approximately	O(1)	Checks every integer individually for ugliness
Optimal Dynamic Programming	O(n)	O(n)	Builds ugly numbers directly in sorted order

Here, k represents the number of divisions needed during factor checking in the brute-force approach.

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

Create an array called ugly_numbers of size n.

This array stores the ugly numbers in ascending order. Initialize the first value as 1 because the sequence always starts with 1. 2. Initialize three pointers:

pointer2
pointer3
pointer5

These pointers indicate which previously generated ugly number should next be multiplied by 2, 3, or 5. 3. Compute the next candidates.

At every iteration:

next2 = ugly_numbers[pointer2] * 2
next3 = ugly_numbers[pointer3] * 3
next5 = ugly_numbers[pointer5] * 5

These represent the next possible ugly numbers generated from each prime factor. 4. Choose the smallest candidate.

The next ugly number must be the minimum among:

next2
next3
next5

Append this minimum value to the sequence. 5. Advance all matching pointers.

If the chosen value equals next2, increment pointer2.

If it equals next3, increment pointer3.

If it equals next5, increment pointer5.

This step is critical because the same ugly number may be produced multiple ways.

Example:

6 = 2 × 3
6 = 3 × 2

Advancing all matching pointers prevents duplicates. 6. Repeat until the array contains n ugly numbers. 7. Return the final value in the array.

Why it works

The algorithm maintains the invariant that ugly_numbers is always sorted and contains only valid ugly numbers.

Every newly generated number comes from multiplying an existing ugly number by 2, 3, or 5, so every produced number is guaranteed to be ugly.

Because we always select the minimum available candidate, the sequence remains sorted in ascending order. Advancing all matching pointers ensures duplicates are skipped while still preserving completeness.

Python Solution

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly_numbers = [0] * n
        ugly_numbers[0] = 1

        pointer2 = 0
        pointer3 = 0
        pointer5 = 0

        for index in range(1, n):
            next2 = ugly_numbers[pointer2] * 2
            next3 = ugly_numbers[pointer3] * 3
            next5 = ugly_numbers[pointer5] * 5

            next_ugly = min(next2, next3, next5)
            ugly_numbers[index] = next_ugly

            if next_ugly == next2:
                pointer2 += 1

            if next_ugly == next3:
                pointer3 += 1

            if next_ugly == next5:
                pointer5 += 1

        return ugly_numbers[-1]

The implementation begins by allocating an array to store the ugly numbers. The first element is initialized to 1, which forms the base of the sequence.

The three pointers track which previously generated ugly number should be multiplied next by 2, 3, and 5.

Inside the loop, the algorithm computes three candidate values and chooses the minimum among them. That minimum becomes the next ugly number.

The most important part of the implementation is the pointer advancement logic. Multiple if statements are used instead of elif because several candidates may be equal simultaneously. Advancing all matching pointers prevents duplicates from entering the sequence.

Finally, the last generated value is returned.

Go Solution

func nthUglyNumber(n int) int {
    uglyNumbers := make([]int, n)
    uglyNumbers[0] = 1

    pointer2 := 0
    pointer3 := 0
    pointer5 := 0

    for i := 1; i < n; i++ {
        next2 := uglyNumbers[pointer2] * 2
        next3 := uglyNumbers[pointer3] * 3
        next5 := uglyNumbers[pointer5] * 5

        nextUgly := min(next2, min(next3, next5))
        uglyNumbers[i] = nextUgly

        if nextUgly == next2 {
            pointer2++
        }

        if nextUgly == next3 {
            pointer3++
        }

        if nextUgly == next5 {
            pointer5++
        }
    }

    return uglyNumbers[n-1]
}

func min(a int, b int) int {
    if a < b {
        return a
    }

    return b
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in integer minimum function for multiple values, a helper min function is added.

Slices are used to store the ugly numbers dynamically. Integer overflow is not a concern because the problem guarantees the result fits within a 32-bit signed integer for n <= 1690.

The pointer advancement logic again uses separate if statements to correctly handle duplicate candidate values.

Worked Examples

Example 1

Input:

n = 10

We generate ugly numbers step by step.

Initial state:

Index	Ugly Numbers
0	1

Pointers:

Pointer	Value
pointer2	0
pointer3	0
pointer5	0

Now iterate.

Step	next2	next3	next5	Chosen	Sequence
1	2	3	5	2	1, 2
2	4	3	5	3	1, 2, 3
3	4	6	5	4	1, 2, 3, 4
4	6	6	5	5	1, 2, 3, 4, 5
5	6	6	10	6	1, 2, 3, 4, 5, 6
6	8	9	10	8	1, 2, 3, 4, 5, 6, 8
7	10	9	10	9	1, 2, 3, 4, 5, 6, 8, 9
8	10	12	10	10	1, 2, 3, 4, 5, 6, 8, 9, 10
9	12	12	15	12	1, 2, 3, 4, 5, 6, 8, 9, 10, 12

Final answer:

Example 2

Input:

n = 1

Initial array:

Index	Value
0	1

Since the sequence already contains one ugly number, the algorithm immediately returns:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each ugly number is generated once
Space	O(n)	The DP array stores all generated ugly numbers

The algorithm performs a constant amount of work for each of the n iterations. Each pointer only moves forward and never backward, so the total work remains linear.

The space complexity is also linear because we store all generated ugly numbers in the array.

Test Cases

solution = Solution()

assert solution.nthUglyNumber(1) == 1       # smallest valid input
assert solution.nthUglyNumber(2) == 2       # first generated ugly number
assert solution.nthUglyNumber(3) == 3       # simple progression
assert solution.nthUglyNumber(4) == 4       # power of 2
assert solution.nthUglyNumber(5) == 5       # includes factor 5
assert solution.nthUglyNumber(6) == 6       # duplicate generation case
assert solution.nthUglyNumber(7) == 8       # skips non-ugly number 7
assert solution.nthUglyNumber(10) == 12     # provided example
assert solution.nthUglyNumber(11) == 15     # continued sequence correctness
assert solution.nthUglyNumber(15) == 24     # larger sequence check
assert solution.nthUglyNumber(100) == 1536  # medium-sized test
assert solution.nthUglyNumber(1690) == 2123366400  # maximum constraint

Test	Why
`n = 1`	Validates base case handling
`n = 2`	Confirms first generated value
`n = 6`	Tests duplicate candidate handling
`n = 7`	Ensures non-ugly numbers are skipped
`n = 10`	Verifies provided example
`n = 100`	Confirms correctness on larger input
`n = 1690`	Validates maximum constraint handling

Edge Cases

Edge Case 1: `n = 1`

This is the smallest possible input and is easy to mishandle if the implementation assumes generation must always occur.

The algorithm handles this correctly because the array is initialized with 1 as the first ugly number. If n is 1, the loop never executes, and the method immediately returns 1.

Edge Case 2: Duplicate Generation

Some ugly numbers can be produced through multiple multiplication paths.

For example:

6 = 2 × 3
6 = 3 × 2

A buggy implementation might insert duplicates into the sequence if only one pointer advances.

This implementation avoids duplicates by incrementing every pointer whose candidate matches the chosen ugly number.

Edge Case 3: Large Input Near Constraint Limit

The largest input is 1690, which generates relatively large ugly numbers.

A brute-force implementation may become too slow because it wastes time checking many non-ugly integers.

The dynamic programming approach remains efficient because it generates only valid ugly numbers directly. The linear complexity ensures excellent performance even at the maximum constraint.

LeetCode 264 - Ugly Number II

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Dynamic Programming Approach

Approach Comparison

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Complexity Analysis

Test Cases

Edge Cases

Edge Case 1: n = 1

Edge Case 2: Duplicate Generation

Edge Case 3: Large Input Near Constraint Limit

Edge Case 1: `n = 1`