Coding Interview PatternsUgly Number II
MediumTop K Elements
Ugly Number II
Explanation & Solution
Description
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
Note that 1 is typically treated as an ugly number.
Input: n = 10
Output: 12
Explanation: The first 10 ugly numbers are [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]. The 10th ugly number is 12.
Constraints
1 <= n <= 1690
Approach
Top K Elements pattern
1. Initialize the DP Array and Three Pointers
- Create a
dparray of sizenwheredp[i]will hold the(i+1)th ugly number. - Set
dp[0] = 1since 1 is the first ugly number. - Initialize three pointers
i2 = 0,i3 = 0,i5 = 0— each tracks which ugly number should next be multiplied by 2, 3, or 5 respectively.
2. Generate Ugly Numbers One by One
- For each position
ifrom 1 ton - 1: - Compute three candidates:
dp[i2] * 2,dp[i3] * 3,dp[i5] * 5. - The next ugly number is the minimum of these three candidates.
- Store it in
dp[i].
3. Advance the Pointers
- After choosing the minimum, advance every pointer whose candidate equals the chosen value.
- Using
if(notelse if) for all three checks ensures duplicates are skipped — for example, 6 can be produced by both2 * 3and3 * 2, so bothi2andi3must advance.
4. Return the Result
- After filling the array,
dp[n - 1]holds the nth ugly number.
Key Insight
- Every ugly number is formed by multiplying a smaller ugly number by 2, 3, or 5. The three-pointer technique merges three sorted sequences (
dp[i]*2,dp[i]*3,dp[i]*5) in order, similar to merging sorted lists.
Time
O(n)a single pass fills the array.Space
O(n)for the `dp` array storing all n ugly numbers.