NUHMAN.com

Introduction

LeetCode 264: Ugly Number II builds upon Ugly Number (263). This time, instead of checking if a number is ugly, you need to generate the nth ugly number, where ugly numbers are positive integers with only 2, 3, and 5 as prime factors.

Problem Statement

Given an integer n, return the nth ugly number.

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

Examples

python

Input: n = 10
Output: 12
Explanation: The first 10 ugly numbers are:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

✅ Step-by-Step Solution in Python

There are two main approaches:

• Min Heap (priority queue)
• Dynamic Programming with pointers ← Most optimal and elegant

We’ll use the DP with 3 pointers method here.

💡 Key Insight

Each ugly number is generated by multiplying previous ugly numbers by 2, 3, or 5.

We maintain:

• A list uglies to store the sequence
• Three pointers i2, i3, i5 for the last used multiples of 2, 3, and 5

Step 1: Initialize

python

uglies = [1] * n
i2 = i3 = i5 = 0

Step 2: Generate Ugly Numbers

At each step, the next ugly number is the minimum of:

• uglies[i2] * 2
• uglies[i3] * 3
• uglies[i5] * 5

We add this to the list and increment the respective pointer(s).

✅ Python Code

python

def nthUglyNumber(n: int) -> int:
    uglies = [1] * n
    i2 = i3 = i5 = 0

    for i in range(1, n):
        next2, next3, next5 = uglies[i2] * 2, uglies[i3] * 3, uglies[i5] * 5
        next_ugly = min(next2, next3, next5)
        uglies[i] = next_ugly

        if next_ugly == next2:
            i2 += 1
        if next_ugly == next3:
            i3 += 1
        if next_ugly == next5:
            i5 += 1

    return uglies[-1]

🔍 Explanation

• Start with 1 (the first ugly number).
• At each step, compute candidates from the three primes.
• Append the smallest candidate.
• Advance the corresponding pointer(s) to prevent duplicates.

🧪 Dry Run Example (n = 10)

Generated sequence:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

Result: 12

⏱️ Time and Space Complexity

• Time Complexity: O(n) – One pass through n iterations
• Space Complexity: O(n) – For the uglies list

🆚 Alternate Method: Min Heap

You can also use a min heap to generate numbers in sorted order and use a set to avoid duplicates. It’s elegant but has slightly higher overhead (log n per insertion).

✅ Conclusion

LeetCode 264: Ugly Number II is a classic example of using dynamic programming with multiple pointers to generate a sorted list efficiently.

You’ve learned:

• How to avoid duplicates with smart pointer movement
• How to systematically generate a sequence with known multiplicative rules

Want to go even further? Check out:

• 313. Super Ugly Number – Generalizes this with custom prime factors