LeetCode 264: Ugly Number II Solution in Python – A Step-by-Step Guide

What Is LeetCode 264: Ugly Number II?

In LeetCode 264: Ugly Number II, you’re given an integer n, and your task is to return the nth ugly number in the sequence of ugly numbers, where an ugly number has only 2, 3, or 5 as its prime factors. The sequence starts with 1 (no factors), then 2, 3, 4, 5, 6, 8, 9, 10, 12, and so on. This problem builds on LeetCode 263: Ugly Number, moving from checking a single number to generating a sequence up to the nth term.

Problem Statement

• Input: An integer n.
• Output: An integer—the nth ugly number in the sequence.
• Rules: Ugly numbers have prime factors only of 2, 3, or 5; sequence starts at 1; order matters.

Constraints

• n: 1 to 1690 (due to integer limits and sequence growth).

Examples

• Input: n = 10
• Output: 12 (sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12).
• Input: n = 1
• Output: 1 (first ugly number).
• Input: n = 7
• Output: 8 (sequence: 1, 2, 3, 4, 5, 6, 8).

Understanding the Problem: Finding the nth Ugly Number

To solve LeetCode 264: Ugly Number II in Python, we need to generate ugly numbers in order—starting with 1—and keep going until we reach the nth one. Ugly numbers are products of powers of 2, 3, and 5 (e.g., 1 = 2^0 * 3^0 * 5^0, 6 = 2^1 * 3^1 * 5^0). A simple way—checking every number to see if it’s ugly—works but is way too slow. We’ll use two methods: 1. Best Solution (Dynamic Programming with Multiple Pointers): O(n) time—fast and clever. 2. Alternative Solution (Min-Heap): O(n log n)—steady but uses more memory.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Dynamic Programming with Multiple Pointers

Why This Is the Best Solution

The dynamic programming approach with multiple pointers is the top pick for LeetCode 264 because it runs in O(n) time—super quick—and uses O(n) space to build the sequence directly, avoiding unnecessary checks. It’s like having three helpers pointing to the next numbers to multiply by 2, 3, and 5, picking the smallest each time, which keeps everything smooth and efficient.

How It Works

Picture this solution as running a number factory: you start with 1, then use three assembly lines—one for 2s, one for 3s, and one for 5s—to build new ugly numbers by multiplying existing ones. Each line has a pointer tracking which number it’s working on, and you always pick the smallest result to add next. Here’s how it works, step-by-step, explained simply:

• Step 1: Start with a List:
• Make a list ugly to hold the sequence, starting with [1].
• Step 2: Set Up Pointers:
• Use three pointers: p2, p3, p5, all starting at 0 (pointing to the first ugly number, 1).
• These track which ugly number to multiply by 2, 3, or 5 next.
• Step 3: Build the Sequence:
• For each step up to n:
• Calculate next candidates: ugly[p2] * 2, ugly[p3] * 3, ugly[p5] * 5.
• Pick the smallest one (call it next_ugly).
• Add it to the list.
• Move the pointer(s) forward for whichever factor(s) produced it.
• Step 4: Avoid Duplicates:
• If next_ugly comes from multiple factors (e.g., 6 = 2 * 3 = 3 * 2), move all matching pointers.
• Step 5: Get the nth Number:
• The list grows to size n; return the last one (ugly[n-1]).

It’s like a race where 2, 3, and 5 compete to make the next smallest number—pick the winner and keep going!

Step-by-Step Example

Example: n = 10

• Step 1: ugly = [1], p2 = 0, p3 = 0, p5 = 0.
• Step 2: Build up to 10:
• Next: min(1*2, 1*3, 1*5) = 2, ugly = [1, 2], p2 = 1.
• Next: min(2*2, 1*3, 1*5) = 3, ugly = [1, 2, 3], p3 = 1.
• Next: min(2*2, 3*3, 1*5) = 4, ugly = [1, 2, 3, 4], p2 = 2.
• Next: min(3*2, 3*3, 1*5) = 5, ugly = [1, 2, 3, 4, 5], p5 = 1.
• Next: min(3*2, 3*3, 5*5) = 6, ugly = [1, 2, 3, 4, 5, 6], p2 = 3.
• Next: min(4*2, 3*3, 5*5) = 8, ugly = [1, 2, 3, 4, 5, 6, 8], p2 = 4.
• Next: min(5*2, 3*3, 5*5) = 9, ugly = [1, 2, 3, 4, 5, 6, 8, 9], p3 = 2.
• Next: min(5*2, 9*3, 5*5) = 10, ugly = [1, 2, 3, 4, 5, 6, 8, 9, 10], p2 = 5.
• Next: min(6*2, 9*3, 5*5) = 12, ugly = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12], p2 = 6.
• Step 3: n = 10, return ugly[9] = 12.
• Result: 12.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def nthUglyNumber(self, n: int) -> int:
        # Step 1: Set up the ugly number list
        ugly = [1] * n  # Make room for n numbers, start with 1

        # Step 2: Initialize pointers and factors
        p2 = p3 = p5 = 0  # Start all pointers at index 0
        next2, next3, next5 = 2, 3, 5  # First multiples of 1

        # Step 3: Build the sequence
        for i in range(1, n):
            # Find the smallest next ugly number
            next_ugly = min(next2, next3, next5)
            ugly[i] = next_ugly

            # Step 4: Update pointers for used factors
            if next_ugly == next2:
                p2 += 1
                next2 = ugly[p2] * 2
            if next_ugly == next3:
                p3 += 1
                next3 = ugly[p3] * 3
            if next_ugly == next5:
                p5 += 1
                next5 = ugly[p5] * 5

        # Step 5: Return the nth ugly number
        return ugly[n-1]

• Line 3-4: Create a list of size n, starting with 1.
• Line 6-7: Set pointers to 0 and initial next values (2, 3, 5).
• Line 9-19: Loop n-1 times to fill the list:
• Pick the smallest of next2, next3, next5.
• Add it to ugly.
• Move the pointer(s) forward and update the next value(s) for any factor used.
• Line 21: Return the last (nth) number.

• Time Complexity: O(n)—builds n numbers linearly.
• Space Complexity: O(n)—stores the sequence.

This solution is like a well-oiled machine—three pointers churn out ugly numbers in perfect order!

Alternative Solution: Min-Heap Approach

Why an Alternative Approach?

The min-heap method uses a priority queue to keep track of the next smallest ugly number, like a conveyor belt spitting out numbers in order. It’s a bit slower (O(n log n)) and uses more space, but it’s a fun way to see how a heap can organize things for you.

How It Works

Imagine you’re managing a line of numbers waiting to join the ugly list: you start with 1, multiply it by 2, 3, and 5, and keep picking the smallest one to add next, tossing its multiples into the line. Here’s how it works, step-by-step:

• Step 1: Set Up a Heap:
• Use a min-heap to store potential ugly numbers, starting with 1.
• Step 2: Build the Sequence:
• Pop the smallest number, add it to your list.
• Push its multiples (times 2, 3, 5) into the heap.
• Step 3: Avoid Duplicates:
• Use a set to skip numbers already added (e.g., 6 from 2*3 and 3*2).
• Step 4: Repeat n Times:
• Keep going until you’ve got n numbers.

It’s like a number buffet—grab the smallest dish and refill the tray with its cousins!

Step-by-Step Example

Example: n = 5

• Step 1: Heap = [1], Seen = {1}, Result = [].
• Step 2:
• Pop 1, Result = [1], Add 2, 3, 5 → Heap = [2, 3, 5], Seen = {1, 2, 3, 5}.
• Pop 2, Result = [1, 2], Add 4, 6, 10 → Heap = [3, 5, 4, 6, 10], Seen adds 4, 6, 10.
• Pop 3, Result = [1, 2, 3], Add 6 (skip), 9, 15 → Heap = [4, 5, 6, 10, 9, 15], Seen adds 9, 15.
• Pop 4, Result = [1, 2, 3, 4], Add 8, 12, 20 → Heap = [5, 6, 9, 10, 15, 8, 12, 20], Seen adds 8, 12, 20.
• Pop 5, Result = [1, 2, 3, 4, 5], Done.
• Result: 5.

Code for Min-Heap Approach

Copy codeimport heapq

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # Step 1: Set up heap and seen set
        heap = [1]
        seen = {1}
        factors = [2, 3, 5]

        # Step 2: Get n ugly numbers
        for _ in range(n - 1):
            curr = heapq.heappop(heap)
            for factor in factors:
                next_num = curr * factor
                if next_num not in seen:
                    heapq.heappush(heap, next_num)
                    seen.add(next_num)

        # Step 3: Return the nth number
        return heapq.heappop(heap)

• Time Complexity: O(n log n)—heap operations for n numbers.
• Space Complexity: O(n)—heap and set size.

It’s a steady builder but heavier on resources.

Comparing the Two Solutions

• Best Solution (DP with Pointers):
• Pros: O(n) time, O(n) space, fast and lean.
• Cons: Pointer logic might take a moment to click.
• Alternative Solution (Min-Heap):
• Pros: O(n log n) time, heap makes order clear.
• Cons: O(n) space, slower with heap ops.

DP wins for efficiency.

Additional Examples and Edge Cases

First Few

• n = 1 → 1
• n = 3 → 3

Larger n

• n = 15 → 24 (sequence up to 24)

Both handle these smoothly.

Complexity Breakdown

• DP with Pointers:
• Time: O(n)—linear build.
• Space: O(n)—list size.
• Min-Heap:
• Time: O(n log n)—heap operations.
• Space: O(n)—heap and set.

DP is the speed king.

Key Takeaways

• DP Pointers: Build in order with helpers.
• Min-Heap: Sort with a queue.
• Ugly Numbers: Grow from 2, 3, 5.
• Python Tip: Lists and heaps are versatile—see [Python Basics](/python/basics).

Final Thoughts: Hunt Ugly Numbers Like a Pro

LeetCode 264: Ugly Number II in Python is a thrilling number chase. The DP solution races ahead with pointers, while the min-heap offers a steady climb. Want more? Try LeetCode 263: Ugly Number or LeetCode 313: Super Ugly Number. Ready to hunt? Head to Solve LeetCode 264 on LeetCode and nab that nth ugly number today!