How do you solve Ugly Number II on LeetCode?

Ugly Number II (LeetCode #264) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Ugly numbers are generated by multiplying previous ugly numbers by 2, 3, or 5.

What is the brute force solution for Ugly Number II?

The brute force approach for Ugly Number II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each number sequentially to see if it's an ugly number. This involves checking if the number can be divided by 2, 3, or 5 until it reaches 1. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Ugly Number II?

Ugly Number II uses the following concepts: Hash Table, Math, Dynamic Programming, Heap (Priority Queue). The recommended patterns to study are: Heap (Priority Queue), Dynamic Programming.

What are the interview tips for Ugly Number II?

Always discuss your thought process before jumping into coding. Consider edge cases, such as n = 1, and how your solution handles them. Explain your choice of data structures and algorithms clearly.

What are common mistakes when solving Ugly Number II?

Not using a set to track already generated ugly numbers, leading to duplicates in the heap. Confusing the order of operations when extracting from the heap and generating new numbers.

#264

Ugly Number II

Medium

Hash TableMathDynamic ProgrammingHeap (Priority Queue)Heap (Priority Queue)Dynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach uses a min-heap (or priority queue) to generate ugly numbers efficiently. By multiplying the smallest ugly number by 2, 3, and 5, we can ensure we only generate ugly numbers.

⚙️

Algorithm

3 steps

1Step 1: Initialize a min-heap and add the first ugly number (1).
2Step 2: Use a loop to extract the smallest number from the heap n times.
3Step 3: For each extracted number, multiply it by 2, 3, and 5, and add the results back to the heap if they haven't been added before.

solution.py17 lines

1# Full working Python code
2import heapq
3
4def nthUglyNumber(n):
5    heap = []
6    heapq.heappush(heap, 1)
7    ugly_set = {1}
8    ugly_number = 0
9    for _ in range(n):
10        ugly_number = heapq.heappop(heap)
11        for i in [2, 3, 5]:
12            new_ugly = ugly_number * i
13            if new_ugly not in ugly_set:
14                ugly_set.add(new_ugly)
15                heapq.heappush(heap, new_ugly)
16    return ugly_number
17

ℹ

Complexity note: The time complexity is O(n log n) because we are inserting new ugly numbers into a priority queue, which takes log n time for each insertion, and we do this n times.

1Ugly numbers are generated by multiplying previous ugly numbers by 2, 3, or 5.
2Using a priority queue helps in efficiently generating the next ugly number without checking every integer.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.