#264

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Ugly Number II

Find the nth ugly number, where ugly numbers have prime factors limited to 2, 3, and 5.

hash table math dynamic programming heap priority queue

Problem Statement

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. For example, 6 is an ugly number because its prime factors are 2 and 3. Given an integer n, you are tasked with returning the nth ugly number in the sequence. The sequence starts with 1, and subsequent ugly numbers are generated by multiplying the previous ugly numbers by 2, 3, or 5.

You are asked to find the nth ugly number efficiently, considering that brute force methods, such as checking each number for ugliness, may be too slow. Instead, we can employ a dynamic programming approach, optimizing the calculation by keeping track of multiple factors using a heap or hash table.

Examples

Example 1

Input: n = 10

Output: 12

[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

1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints

1 <= n <= 1690

Solution Approach

State Transition Dynamic Programming

The most efficient solution uses state transition dynamic programming to generate the nth ugly number. We maintain three pointers that track the next potential ugly numbers for 2, 3, and 5. By updating these pointers as we build the sequence, we ensure that we can directly compute the next ugly number in constant time, leading to O(n) time complexity.

Heap-based Optimization

To manage the next possible ugly numbers in an efficient manner, we use a heap (priority queue). By pushing the next ugly numbers generated by multiplying the smallest current ugly number by 2, 3, or 5, we keep track of the smallest number at each step, allowing us to compute the nth ugly number with optimized space complexity of O(n).

Efficient Space Management

By maintaining arrays for the next available ugly number for 2, 3, and 5 and using a heap to store the potential values, we achieve optimal space management while maintaining an O(n) space complexity. This ensures that we don't have to check all numbers up to n, focusing only on the ugly numbers generated by the state transition approach.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity of this approach is O(n) because we are iterating through each number once while calculating the nth ugly number. Space complexity is O(n) due to the storage of arrays and the heap used for tracking the next potential ugly numbers. This is an optimal solution compared to brute force methods, which would be less efficient.

What Interviewers Usually Probe

Look for familiarity with dynamic programming and heap-based approaches.
Evaluate whether the candidate can optimize space complexity while maintaining time efficiency.
Assess how well the candidate can combine multiple data structures (heap, array) to solve a problem.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution by checking each number for ugliness rather than using dynamic programming.
Incorrectly managing the pointers for 2, 3, and 5, which can result in missed ugly numbers.
Using brute force methods that don't leverage the state transition optimization, leading to inefficient solutions.

Follow-up variants

Find the nth ugly number without using a heap, relying purely on dynamic programming.
Optimize the solution for larger values of n, up to the maximum constraint.
Extend the concept of ugly numbers to include other primes, such as 7, 11, etc.

FAQ

What is the state transition dynamic programming approach in Ugly Number II?

The state transition dynamic programming approach in Ugly Number II uses multiple pointers to track the next possible ugly numbers for 2, 3, and 5. By updating these pointers, we generate the ugly number sequence efficiently.

Why is a heap used in the Ugly Number II problem?

A heap is used to track the next smallest ugly number by pushing the results of multiplying the current ugly numbers by 2, 3, and 5, which ensures that we can extract the next smallest number efficiently.

How does the Ugly Number II problem relate to dynamic programming?

The Ugly Number II problem uses dynamic programming to keep track of previously computed ugly numbers and efficiently generate the next numbers in the sequence by utilizing a state transition approach.

What are common mistakes when solving Ugly Number II?

Common mistakes include using brute force to check each number for ugliness and failing to manage the state transitions for 2, 3, and 5 correctly.

How can I optimize my solution for large values of n in Ugly Number II?

To optimize for large values of n, focus on space and time efficiency. Use dynamic programming with a heap to manage the sequence generation while ensuring optimal storage and extraction of values.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h = [1]
        vis = {1}
        ans = 1
        for _ in range(n):
            ans = heappop(h)
            for v in [2, 3, 5]:
                nxt = ans * v
                if nxt not in vis:
                    vis.add(nxt)
                    heappush(h, nxt)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h = [1]
        vis = {1}
        ans = 1
        for _ in range(n):
            ans = heappop(h)
            for v in [2, 3, 5]:
                nxt = ans * v
                if nxt not in vis:
                    vis.add(nxt)
                    heappush(h, nxt)
        return ans

Continue Practicing

#996 number of squareful arrays #268 missing number #241 different ways to add parentheses