Is Ugly Number II easy or hard?

Ugly Number II is generally rated as a medium difficulty problem. The brute-force idea is simple, but identifying the optimized three-pointer dynamic programming pattern requires deeper understanding of sequence generation and duplicate handling.

How to solve Ugly Number II in O(n)?

Use a dynamic programming array where dp[i] stores the ith ugly number. Track three indices for multiples of 2, 3, and 5, compute the next candidate values, and pick the smallest each iteration. Increment the pointer(s) that produced the chosen value to avoid duplicates.

What is the best approach for Ugly Number II?

The most efficient solution uses dynamic programming with three pointers. Maintain pointers for multiples of 2, 3, and 5 and generate the sequence iteratively while keeping it sorted. This approach runs in O(n) time and O(n) space and avoids duplicate values.

What data structure is used in Ugly Number II?

The optimal solution primarily uses an array for dynamic programming and three index pointers. An alternative implementation uses a min-heap (priority queue) combined with a hash set to maintain order and prevent duplicate values.

What is the time complexity of Ugly Number II?

The optimal dynamic programming approach runs in O(n) time because each ugly number is generated once using three pointer comparisons. Space complexity is O(n) to store the sequence. A heap-based approach takes O(n log n) time due to priority queue operations.

Ugly Number II Python or Java solution approach?

Both Python and Java implementations typically use the three-pointer dynamic programming technique. Maintain an array of size n, compute candidates from the current pointers, and update the pointers whenever their multiple is selected. This keeps the sequence sorted and efficient.

Is Ugly Number II asked at Google, Amazon, or Meta?

Ugly Number II appears in interview preparation lists for companies such as Amazon, Google, and Microsoft. The problem tests dynamic programming fundamentals, sequence generation, and pointer optimization techniques.

Description Hints 4 Solution Video 31:09

264. Ugly Number II

Medium49.7% acceptance9 companies

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

Given an integer n, return the n^th ugly number.

Example 1:

Input: n = 10
Output: 12
Explanation: [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
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

1 <= n <= 1690

Asked at 9 companies

Turing Paytm Bloomberg Visa Amazon Microsoft Goldman Sachs

Google Meta

Topics

Hints open one at a time

Hint 1

The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.

Hint 2

An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.

Hint 3

The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.

Hint 4

Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

31:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution