Ugly Number II

Ugly Number II

What is this problem about?

Building on the basic concept, the Ugly Number II interview question asks you to find the $n$-th ugly number. Instead of just checking if a number is ugly, you must generate them in sequence (1, 2, 3, 4, 5, 6, 8, 9, 10, 12...) until you reach the target index. This is a much more complex challenge that requires efficient generation rather than brute-force checking.

Why is this asked in interviews?

This Ugly Number II coding problem is common in interviews at Goldman Sachs and Amazon because it tests your ability to use Dynamic Programming or Heaps to manage state. It requires you to generate numbers in a sorted fashion without duplicates, which is a common requirement in data processing tasks.

Algorithmic pattern used

There are two main Math, Hash Table, Heap (Priority Queue), Dynamic Programming interview patterns for this. The Heap approach involves using a priority queue to always pick the smallest current ugly number and multiply it by 2, 3, and 5 to generate new ones. The Dynamic Programming approach is even more elegant, using three pointers to track the next multiple of 2, 3, and 5, and always choosing the minimum of the three to be the next ugly number in the list.

Example explanation

Suppose we want the 7th ugly number.

1. Start with [1]. Pointers for 2, 3, 5 are all at index 0.
2. Candidates: $1*2=2$, $1*3=3$, $1*5=5$. Min is 2.
3. List: [1, 2]. Pointer for 2 moves to index 1.
4. Candidates: $2*2=4$, $1*3=3$, $1*5=5$. Min is 3.
5. List: [1, 2, 3]. Pointer for 3 moves to index 1.
6. Candidates: $2*2=4$, $2*3=6$, $1*5=5$. Min is 4.
7. List: [1, 2, 3, 4]. Pointer for 2 moves to index 2. ...continue until the 7th element is reached.

Common mistakes candidates make

A common error in the Heap approach is not handling duplicate numbers (e.g., $2*3$ and $3*2$ both equal 6). In the DP approach, candidates often forget to increment all pointers that produce the same minimum value, which also leads to duplicates. Efficiency is also a concern; a brute-force check for every number would be far too slow.

Interview preparation tip

When a problem asks for the "$n$-th" something, think about Dynamic Programming or Priority Queues. These tools are specifically designed to build up a solution step-by-step from smaller sub-problems or to maintain an ordered set of candidates.