277. Ugly Number II
🔗 LeetCode Problem: 264. Ugly Number II
📊 Difficulty: Medium
🏷️ Topics: 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.
Given an integer n, return the nth 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
🌟 Understanding Ugly Numbers
What are ugly numbers?
Ugly numbers: Only have prime factors 2, 3, and 5
First 15 ugly numbers:
1 = 1
2 = 2
3 = 3
4 = 2 × 2
5 = 5
6 = 2 × 3
8 = 2 × 2 × 2
9 = 3 × 3
10 = 2 × 5
12 = 2 × 2 × 3
15 = 3 × 5
16 = 2 × 2 × 2 × 2
18 = 2 × 3 × 3
20 = 2 × 2 × 5
24 = 2 × 2 × 2 × 3
NOT ugly numbers:
7 = 7 (has prime factor 7)
11 = 11 (has prime factor 11)
14 = 2 × 7 (has prime factor 7)
Key Observation:
CRITICAL INSIGHT:
Every ugly number (except 1) is formed by:
- Taking a previous ugly number
- Multiplying by 2, 3, or 5
Example:
1 is ugly
1 × 2 = 2 (ugly)
1 × 3 = 3 (ugly)
2 × 2 = 4 (ugly)
2 × 3 = 6 (ugly)
3 × 2 = 6 (ugly) - duplicate!
Each ugly number = previous ugly × {2, 3, or 5}
This is the KEY to solving efficiently!
🌟 The Natural Thinking Process
When you first see this problem:
Question: Find the nth ugly number
First Thought: "Check each number starting from 1"
- For each number, check if it's ugly
- Count ugly numbers
- Stop when count = n
Is this optimal? NO, but it WORKS!
Let's try it first.
The Evolution:
BRUTE FORCE THINKING:
"Check 1, 2, 3, 4, 5, 6, 7, 8..."
"For each, divide by 2,3,5 repeatedly"
Time: O(n × log m) where m is the nth ugly number
Problem: m can be VERY large!
⬇
REALIZATION 1:
"I'm checking NON-ugly numbers too (7, 11, 13...)"
"Waste of time!"
"What if I GENERATE only ugly numbers?"
⬇
OPTIMIZATION 1: Min-Heap
"Generate candidates by multiplying previous ugly by 2,3,5"
"Use min-heap to get smallest candidate"
Time: O(n log n) - better!
But uses O(n) space for heap
⬇
REALIZATION 2:
"I'm generating same number multiple ways (duplicates!)"
"Need to track what I've seen"
"What if I track THREE separate sequences?"
⬇
OPTIMIZATION 2: Three Pointers (DP)
"Maintain three pointers for ×2, ×3, ×5"
"Always pick minimum"
Time: O(n), Space: O(n) - OPTIMAL!
🎯 Approach 1: Brute Force - Check Each Number ⭐
The First Natural Solution
The Thought Process:
Step 1: Read problem
"Find nth ugly number"
Step 2: How to check if ugly?
"Divide by 2 while divisible"
"Divide by 3 while divisible"
"Divide by 5 while divisible"
"If result is 1 → ugly!"
Step 3: Generate sequence
"Start from 1, check each number"
"Count ugly numbers until count = n"
This is slow for large n, but let's code it!
Helper: Is Number Ugly?
private boolean isUgly(int num) {
if (num <= 0) return false;
// Divide by 2 while possible
while (num % 2 == 0) {
num /= 2;
}
// Divide by 3 while possible
while (num % 3 == 0) {
num /= 3;
}
// Divide by 5 while possible
while (num % 5 == 0) {
num /= 5;
}
// If only factors were 2,3,5 → result is 1
return num == 1;
}
Visual Tracking - Find 10th Ugly Number
Goal: Find 10th ugly number
═══════════════════════════════════════════════════════════════
CHECK NUMBERS ONE BY ONE
═══════════════════════════════════════════════════════════════
num=1: Is 1 ugly?
No factors to divide
Result: 1 → YES, ugly!
Count: 1
num=2: Is 2 ugly?
2 ÷ 2 = 1
Result: 1 → YES, ugly!
Count: 2
num=3: Is 3 ugly?
3 ÷ 3 = 1
Result: 1 → YES, ugly!
Count: 3
num=4: Is 4 ugly?
4 ÷ 2 = 2 ÷ 2 = 1
Result: 1 → YES, ugly!
Count: 4
num=5: Is 5 ugly?
5 ÷ 5 = 1
Result: 1 → YES, ugly!
Count: 5
num=6: Is 6 ugly?
6 ÷ 2 = 3 ÷ 3 = 1
Result: 1 → YES, ugly!
Count: 6
num=7: Is 7 ugly?
Can't divide by 2,3,5
Result: 7 → NO, not ugly! ✗
Count: 6 (unchanged)
num=8: Is 8 ugly?
8 ÷ 2 = 4 ÷ 2 = 2 ÷ 2 = 1
Result: 1 → YES, ugly!
Count: 7
num=9: Is 9 ugly?
9 ÷ 3 = 3 ÷ 3 = 1
Result: 1 → YES, ugly!
Count: 8
num=10: Is 10 ugly?
10 ÷ 2 = 5 ÷ 5 = 1
Result: 1 → YES, ugly!
Count: 9
num=11: Is 11 ugly?
Can't divide by 2,3,5
Result: 11 → NO, not ugly! ✗
Count: 9 (unchanged)
num=12: Is 12 ugly?
12 ÷ 2 = 6 ÷ 2 = 3 ÷ 3 = 1
Result: 1 → YES, ugly!
Count: 10 ← REACHED n=10!
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
10th ugly number: 12 ✓
Ugly numbers found: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
Numbers checked: 12
Wasted checks: 7, 11 (not ugly)
Implementation
/**
* Brute Force: Check each number
* Time: O(n × log m) where m is the nth ugly number
* Space: O(1)
*/
class Solution {
public int nthUglyNumber(int n) {
int count = 0;
int num = 1;
while (count < n) {
if (isUgly(num)) {
count++;
}
if (count < n) {
num++;
}
}
return num;
}
private boolean isUgly(int num) {
if (num <= 0) return false;
while (num % 2 == 0) num /= 2;
while (num % 3 == 0) num /= 3;
while (num % 5 == 0) num /= 5;
return num == 1;
}
}
⏰ Time: O(n × log m) - Check n ugly numbers, each check O(log m)
💾 Space: O(1)
Why This is Slow:
Problem: We check MANY non-ugly numbers!
For n=10: Check 12 numbers (2 wasted)
For n=100: Check ~200 numbers (100 wasted)
For n=1690: Check ~850,000 numbers! 😱
The 1690th ugly number is 2,123,366,400
We'd check 2 BILLION numbers!
Bottleneck: Checking non-ugly numbers is wasteful!
💡 The First AHA Moment
PROBLEM ANALYSIS:
"I'm checking 7, 11, 13, 17, 19, 23..."
"None of these are ugly!"
"Complete waste of time!"
KEY INSIGHT:
"What if I ONLY GENERATE ugly numbers?"
Every ugly number = previous ugly × {2, 3, or 5}
From 1: Generate 1×2=2, 1×3=3, 1×5=5
From 2: Generate 2×2=4, 2×3=6, 2×5=10
From 3: Generate 3×2=6, 3×3=9, 3×5=15
...
ONLY generate ugly numbers!
Never check non-ugly!
How to pick next? Use MIN-HEAP!
🎯 Approach 2: Min-Heap - Generate Only Ugly Numbers ⭐⭐
The Better Solution
The Evolution of Thought:
Brute Force: Check every number (wasteful)
⬇
Question: "Can I generate ONLY ugly numbers?"
⬇
Answer: "YES! Each ugly = previous ugly × {2,3,5}"
⬇
Better Idea: "Use MIN-HEAP to get smallest candidate!"
Understanding the Generation Process
GENERATION STRATEGY:
Start with 1 (first ugly)
Generate candidates:
1 × 2 = 2
1 × 3 = 3
1 × 5 = 5
Pick smallest: 2
Generate from 2:
2 × 2 = 4
2 × 3 = 6
2 × 5 = 10
Current candidates: [3, 5, 4, 6, 10]
Pick smallest: 3
Generate from 3:
3 × 2 = 6 (duplicate!)
3 × 3 = 9
3 × 5 = 15
Min-heap helps us:
1. Always get smallest candidate
2. Track what we've seen (avoid duplicates)
Visual Tracking - Find 10th Ugly Number
Goal: Find 10th ugly number using min-heap
═══════════════════════════════════════════════════════════════
INITIALIZATION
═══════════════════════════════════════════════════════════════
Min-Heap: [1]
Seen: {1}
Ugly count: 0
═══════════════════════════════════════════════════════════════
STEP 1: Get 1st ugly number
═══════════════════════════════════════════════════════════════
Poll from heap: 1
Ugly[1] = 1 ✓
Generate candidates from 1:
1 × 2 = 2 (not in seen)
1 × 3 = 3 (not in seen)
1 × 5 = 5 (not in seen)
Add to heap: [2, 3, 5]
Seen: {1, 2, 3, 5}
═══════════════════════════════════════════════════════════════
STEP 2: Get 2nd ugly number
═══════════════════════════════════════════════════════════════
Heap: [2, 3, 5]
Poll smallest: 2
Ugly[2] = 2 ✓
Generate from 2:
2 × 2 = 4 (not in seen)
2 × 3 = 6 (not in seen)
2 × 5 = 10 (not in seen)
Add to heap: [3, 5, 4, 6, 10]
↑
min (heap property)
Seen: {1, 2, 3, 5, 4, 6, 10}
═══════════════════════════════════════════════════════════════
STEP 3: Get 3rd ugly number
═══════════════════════════════════════════════════════════════
Heap: [3, 5, 4, 6, 10]
Poll smallest: 3
Ugly[3] = 3 ✓
Generate from 3:
3 × 2 = 6 (already in seen!) ← DUPLICATE
3 × 3 = 9 (not in seen)
3 × 5 = 15 (not in seen)
Add new ones: [4, 5, 6, 10, 9, 15]
Seen: {1, 2, 3, 4, 5, 6, 10, 9, 15}
═══════════════════════════════════════════════════════════════
STEP 4: Get 4th ugly number
═══════════════════════════════════════════════════════════════
Heap: [4, 5, 6, 10, 9, 15]
Poll smallest: 4
Ugly[4] = 4 ✓
Generate from 4:
4 × 2 = 8 (not in seen)
4 × 3 = 12 (not in seen)
4 × 5 = 20 (not in seen)
Add to heap: [5, 6, 9, 10, 15, 8, 12, 20]
Seen: {..., 8, 12, 20}
═══════════════════════════════════════════════════════════════
STEP 5: Get 5th ugly number
═══════════════════════════════════════════════════════════════
Heap: [5, 6, 9, 10, 15, 8, 12, 20]
Poll smallest: 5
Ugly[5] = 5 ✓
Generate from 5:
5 × 2 = 10 (already in seen!) ← DUPLICATE
5 × 3 = 15 (already in seen!) ← DUPLICATE
5 × 5 = 25 (not in seen)
Add new: [6, 8, 9, 10, 12, 15, 20, 25]
═══════════════════════════════════════════════════════════════
STEP 6: Get 6th ugly number
═══════════════════════════════════════════════════════════════
Heap: [6, 8, 9, 10, 12, 15, 20, 25]
Poll smallest: 6
Ugly[6] = 6 ✓
Generate from 6:
6 × 2 = 12 (duplicate)
6 × 3 = 18 (new)
6 × 5 = 30 (new)
Add: [8, 9, 10, 12, 15, 20, 25, 18, 30]
═══════════════════════════════════════════════════════════════
STEP 7-10: Continue similarly
═══════════════════════════════════════════════════════════════
Step 7: Poll 8 → Ugly[7] = 8
Step 8: Poll 9 → Ugly[8] = 9
Step 9: Poll 10 → Ugly[9] = 10
Step 10: Poll 12 → Ugly[10] = 12 ✓
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
10th ugly number: 12 ✓
Sequence: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
Key Observations:
✓ Only generated ugly numbers (no 7, 11, etc.)
✓ Used min-heap to always get smallest
✓ Used HashSet to avoid duplicates
✓ Much faster than brute force!
Implementation
import java.util.*;
/**
* Min-Heap with generation
* Time: O(n log n)
* Space: O(n)
*/
class Solution {
public int nthUglyNumber(int n) {
// Min-heap to get smallest candidate
PriorityQueue<Long> minHeap = new PriorityQueue<>();
// HashSet to avoid duplicates
Set<Long> seen = new HashSet<>();
// Start with 1
minHeap.offer(1L);
seen.add(1L);
long ugly = 1L;
for (int i = 0; i < n; i++) {
// Get smallest candidate
ugly = minHeap.poll();
// Generate new candidates
for (int factor : new int[]{2, 3, 5}) {
long newUgly = ugly * factor;
if (!seen.contains(newUgly)) {
minHeap.offer(newUgly);
seen.add(newUgly);
}
}
}
return (int) ugly;
}
}
⏰ Time: O(n log n) - n iterations, each with heap operations
💾 Space: O(n) - Heap and HashSet storage
Why This is Better:
✓ Only generates ugly numbers (no wasted checks!)
✓ Uses min-heap to get smallest efficiently
✓ HashSet prevents duplicates
But... can we do better?
- O(n log n) is good
- But O(n) space for heap + set
- Can we achieve O(n) time with less overhead?
💡 The Second AHA Moment
PROBLEM ANALYSIS:
Min-Heap approach generates candidates:
From 1: 2, 3, 5
From 2: 4, 6, 10
From 3: 6 (dup!), 9, 15
...
OBSERVATION:
"I'm generating duplicates!"
"6 comes from both 2×3 and 3×2"
"10 comes from both 2×5 and 5×2"
KEY INSIGHT:
"What if I track THREE separate sequences?"
Sequence ×2: 1×2, 2×2, 3×2, 4×2, 5×2...
Sequence ×3: 1×3, 2×3, 3×3, 4×3, 5×3...
Sequence ×5: 1×5, 2×5, 3×5, 4×5, 5×5...
At each step:
- Pick minimum of three
- Advance pointer that gave minimum
- Automatically handles duplicates!
This is DYNAMIC PROGRAMMING! 🎯
🎯 Approach 3: Three Pointers DP (Optimal) ⭐⭐⭐
The Optimal Solution
The Evolution of Thought:
Brute Force: Check all numbers
⬇
Min-Heap: Generate only ugly
⬇
Question: "Can I avoid duplicates altogether?"
⬇
Answer: "Track three sequences with pointers!"
⬇
Optimal: Three pointers DP - O(n) time, O(n) space
Understanding Three Pointers
THE BRILLIANT INSIGHT:
Maintain array: ugly[1..n]
Maintain three pointers: p2, p3, p5
Next candidates:
ugly[p2] × 2
ugly[p3] × 3
ugly[p5] × 5
Pick minimum of three → that's next ugly number
Advance pointer(s) that gave minimum
WHY Advance Pointer That Gave Minimum? - The Critical Reasoning
The Core Question:
We have: ugly[p2]×2, ugly[p3]×3, ugly[p5]×5
We picked minimum and added to array.
Question: Which pointer(s) should we advance? Why?
Answer Through Reasoning:
PRINCIPLE: Each pointer represents a SEQUENCE
Sequence from ×2: [1×2, 2×2, 3×2, 4×2, 5×2, 6×2, ...]
[2, 4, 6, 8, 10, 12, ...]
↑
p2 points here initially
Sequence from ×3: [1×3, 2×3, 3×3, 4×3, 5×3, 6×3, ...]
[3, 6, 9, 12, 15, 18, ...]
↑
p3 points here initially
Sequence from ×5: [1×5, 2×5, 3×5, 4×5, 5×5, 6×5, ...]
[5, 10, 15, 20, 25, 30, ...]
↑
p5 points here initially
GOAL: Merge these three sequences in sorted order!
Think of it like merging three sorted lists!
Detailed Reasoning - Step by Step:
STEP 1: Initial state
═══════════════════════════════════════════════════════════════
ugly = [1, ?, ?, ?, ...]
p2 = p3 = p5 = 0 (all point to ugly[0] = 1)
Sequences and what each pointer sees:
×2 sequence: p2 → ugly[0]×2 = 1×2 = 2, then 2×2, 3×2, ...
×3 sequence: p3 → ugly[0]×3 = 1×3 = 3, then 2×3, 3×3, ...
×5 sequence: p5 → ugly[0]×5 = 1×5 = 5, then 2×5, 3×5, ...
Candidates: [2, 3, 5]
Minimum: 2
ugly[1] = 2 ✓
QUESTION: Which pointer to advance?
REASONING:
We just used "2" from the ×2 sequence
If we DON'T advance p2:
Next time, ×2 sequence gives: ugly[0]×2 = 2 again!
We'd keep getting 2 forever! ✗
If we DO advance p2:
Next time, ×2 sequence gives: ugly[1]×2 = 2×2 = 4 ✓
We move forward in the ×2 sequence!
What about p3 and p5?
They didn't give minimum (3 and 5 are still candidates)
We haven't used them yet!
DON'T advance them - they're still valid candidates!
RULE: Advance the pointer whose sequence gave the minimum!
New state:
p2 = 1 (moved forward)
p3 = 0 (stayed - 3 still available)
p5 = 0 (stayed - 5 still available)
═══════════════════════════════════════════════════════════════
STEP 2: After picking 2
═══════════════════════════════════════════════════════════════
ugly = [1, 2, ?, ?, ...]
p2 = 1, p3 = 0, p5 = 0
Sequences now:
×2 sequence: p2 → ugly[1]×2 = 2×2 = 4
×3 sequence: p3 → ugly[0]×3 = 1×3 = 3 (still!)
×5 sequence: p5 → ugly[0]×5 = 1×5 = 5 (still!)
Candidates: [4, 3, 5]
Minimum: 3
ugly[2] = 3 ✓
REASONING:
We used "3" from ×3 sequence
Advance p3 to get next value from ×3 sequence
DON'T advance p2 (didn't give min)
DON'T advance p5 (didn't give min)
New state:
p2 = 1 (stayed)
p3 = 1 (moved forward - we used this)
p5 = 0 (stayed)
What if We DON'T Follow This Rule?
COUNTER-EXAMPLE: What if we advance WRONG pointer?
State: ugly = [1, 2, ?, ...]
p2 = 1, p3 = 0, p5 = 0
Candidates: [4, 3, 5]
Minimum: 3
CORRECT: Advance p3
Result: [1, 2, 3, 4, 5, 6, ...] ✓
WRONG: Advance p2 instead
Next candidates: ugly[2]×2, ugly[0]×3, ugly[0]×5
= 3×2, 1×3, 1×5
= 6, 3, 5
But ugly[2] = 3!
So we'd compute: 3×2 = 6
Candidates: [6, 3, 5]
We'd pick 3 AGAIN! ✗
Duplicate! Array becomes [1, 2, 3, 3, ...] ✗
OR if we skip duplicates, we'd pick 5 next
Array becomes [1, 2, 3, 5, ...] ✗
We MISSED 4! Not in sorted order!
WRONG: Advance p5 instead
Similar problems - wrong order!
CONCLUSION: MUST advance the pointer that gave minimum!
Special Case: Multiple Pointers Give Same Minimum (DUPLICATES)
EXAMPLE: When does this happen?
ugly = [1, 2, 3, 4, 5, ?, ...]
p2 = 2, p3 = 1, p5 = 0
Candidates:
ugly[2] × 2 = 3 × 2 = 6
ugly[1] × 3 = 2 × 3 = 6 ← SAME!
ugly[0] × 5 = 1 × 5 = 5
Minimum: 5 (from p5)
ugly[5] = 5, advance p5
p2 = 2, p3 = 1, p5 = 1
Next iteration:
Candidates:
ugly[2] × 2 = 3 × 2 = 6
ugly[1] × 3 = 2 × 3 = 6 ← BOTH give 6!
ugly[1] × 5 = 2 × 5 = 10
Minimum: 6
QUESTION: Should we advance just p2? Just p3? Or BOTH?
REASONING:
If we advance ONLY p2:
p2 = 3, p3 = 1, p5 = 1
Next candidates:
ugly[3] × 2 = 4 × 2 = 8
ugly[1] × 3 = 2 × 3 = 6 ← 6 AGAIN!
ugly[1] × 5 = 2 × 5 = 10
We'd pick 6 again! ✗
Duplicate in array!
If we advance ONLY p3:
Same problem - p2 still gives 6!
If we advance BOTH p2 AND p3:
p2 = 3, p3 = 2, p5 = 1
Next candidates:
ugly[3] × 2 = 4 × 2 = 8
ugly[2] × 3 = 3 × 3 = 9
ugly[1] × 5 = 2 × 5 = 10
All different! ✓
No duplicates!
RULE FOR DUPLICATES:
Advance ALL pointers that gave the minimum!
This ensures each sequence moves past that value!
CODE:
if (nextUgly == next2) p2++; // Not else-if!
if (nextUgly == next3) p3++; // Check all!
if (nextUgly == next5) p5++; // Advance all matches!
Visual Analogy - Merging Sorted Lists:
Think of three sorted lists being merged:
List A (×2): [2, 4, 6, 8, 10, 12, ...]
↑
p2
List B (×3): [3, 6, 9, 12, 15, 18, ...]
↑
p3
List C (×5): [5, 10, 15, 20, 25, 30, ...]
↑
p5
To merge in sorted order:
Step 1: Compare heads: 2, 3, 5
Pick 2 (minimum)
Advance pointer in List A (we used it!)
List A: [2, 4, 6, 8, 10, 12, ...]
↑
p2
List B: [3, 6, 9, 12, 15, 18, ...]
↑
p3
List C: [5, 10, 15, 20, 25, 30, ...]
↑
p5
Step 2: Compare heads: 4, 3, 5
Pick 3 (minimum)
Advance pointer in List B
This is EXACTLY what we're doing!
Just that our "lists" are generated on-the-fly
using the ugly numbers we've already found!
GOLDEN RULE:
When you use an element from a sequence,
you MUST advance that sequence's pointer
to get the next element from it!
Otherwise, you'll keep getting the same element!
Summary - The Complete Logic:
WHY advance pointer that gave minimum?
1. PREVENTS STAGNATION:
Not advancing → same value forever
2. MAINTAINS SORTED ORDER:
Each sequence is sorted
Picking minimum + advancing = merged sorted sequence
3. HANDLES DUPLICATES:
Multiple sequences can produce same value (6 = 2×3 = 3×2)
Advance ALL that match → no duplicates
4. GENERATES ALL UGLY NUMBERS:
Each ugly appears in at least one sequence
By advancing after use, we eventually process all
5. OPTIMAL EFFICIENCY:
Each ugly number generated exactly once
O(n) time - can't be better!
This is the MAGIC of the three-pointer approach! ✨
Visual Tracking - Find First 10 Ugly Numbers
Goal: Generate first 10 ugly numbers using three pointers
ugly = [1, ?, ?, ?, ?, ?, ?, ?, ?, ?]
p2 = p3 = p5 = 0
═══════════════════════════════════════════════════════════════
STEP 1: Find ugly[1]
═══════════════════════════════════════════════════════════════
ugly = [1, ?, ?, ?, ?, ?, ?, ?, ?, ?]
↑
p2,p3,p5
Candidates:
ugly[p2] × 2 = ugly[0] × 2 = 1 × 2 = 2
ugly[p3] × 3 = ugly[0] × 3 = 1 × 3 = 3
ugly[p5] × 5 = ugly[0] × 5 = 1 × 5 = 5
Minimum: 2
ugly[1] = 2 ✓
Advance p2 (it gave minimum)
ugly = [1, 2, ?, ?, ?, ?, ?, ?, ?, ?]
↑ ↑
p3,p5 p2
State: p2=1, p3=0, p5=0
═══════════════════════════════════════════════════════════════
STEP 2: Find ugly[2]
═══════════════════════════════════════════════════════════════
ugly = [1, 2, ?, ?, ?, ?, ?, ?, ?, ?]
↑ ↑
p3,p5 p2
Candidates:
ugly[p2] × 2 = ugly[1] × 2 = 2 × 2 = 4
ugly[p3] × 3 = ugly[0] × 3 = 1 × 3 = 3
ugly[p5] × 5 = ugly[0] × 5 = 1 × 5 = 5
Minimum: 3
ugly[2] = 3 ✓
Advance p3
ugly = [1, 2, 3, ?, ?, ?, ?, ?, ?, ?]
↑ ↑
p5 p3
p2
State: p2=1, p3=1, p5=0
═══════════════════════════════════════════════════════════════
STEP 3: Find ugly[3]
═══════════════════════════════════════════════════════════════
ugly = [1, 2, 3, ?, ?, ?, ?, ?, ?, ?]
Candidates:
ugly[1] × 2 = 2 × 2 = 4
ugly[1] × 3 = 2 × 3 = 6
ugly[0] × 5 = 1 × 5 = 5
Minimum: 4
ugly[3] = 4 ✓
Advance p2
ugly = [1, 2, 3, 4, ?, ?, ?, ?, ?, ?]
↑ ↑ ↑
p5 p3 p2
State: p2=2, p3=1, p5=0
═══════════════════════════════════════════════════════════════
STEP 4: Find ugly[4]
═══════════════════════════════════════════════════════════════
Candidates:
ugly[2] × 2 = 3 × 2 = 6
ugly[1] × 3 = 2 × 3 = 6
ugly[0] × 5 = 1 × 5 = 5
Minimum: 5
ugly[4] = 5 ✓
Advance p5
State: p2=2, p3=1, p5=1
═══════════════════════════════════════════════════════════════
STEP 5: Find ugly[5]
═══════════════════════════════════════════════════════════════
Candidates:
ugly[2] × 2 = 3 × 2 = 6
ugly[1] × 3 = 2 × 3 = 6
ugly[1] × 5 = 2 × 5 = 10
Minimum: 6
IMPORTANT: Both p2 and p3 give 6 (DUPLICATE!)
Solution: Advance BOTH p2 and p3!
ugly[5] = 6 ✓
Advance p2 AND p3 (both gave 6)
State: p2=3, p3=2, p5=1
═══════════════════════════════════════════════════════════════
STEP 6: Find ugly[6]
═══════════════════════════════════════════════════════════════
ugly = [1, 2, 3, 4, 5, 6, ?, ?, ?, ?]
Candidates:
ugly[3] × 2 = 4 × 2 = 8
ugly[2] × 3 = 3 × 3 = 9
ugly[1] × 5 = 2 × 5 = 10
Minimum: 8
ugly[6] = 8 ✓
Advance p2
State: p2=4, p3=2, p5=1
═══════════════════════════════════════════════════════════════
STEP 7: Find ugly[7]
═══════════════════════════════════════════════════════════════
Candidates:
ugly[4] × 2 = 5 × 2 = 10
ugly[2] × 3 = 3 × 3 = 9
ugly[1] × 5 = 2 × 5 = 10
Minimum: 9
ugly[7] = 9 ✓
Advance p3
State: p2=4, p3=3, p5=1
═══════════════════════════════════════════════════════════════
STEP 8: Find ugly[8]
═══════════════════════════════════════════════════════════════
Candidates:
ugly[4] × 2 = 5 × 2 = 10
ugly[3] × 3 = 4 × 3 = 12
ugly[1] × 5 = 2 × 5 = 10
Minimum: 10
Both p2 and p5 give 10!
Advance BOTH
ugly[8] = 10 ✓
State: p2=5, p3=3, p5=2
═══════════════════════════════════════════════════════════════
STEP 9: Find ugly[9]
═══════════════════════════════════════════════════════════════
Candidates:
ugly[5] × 2 = 6 × 2 = 12
ugly[3] × 3 = 4 × 3 = 12
ugly[2] × 5 = 3 × 5 = 15
Minimum: 12
Both p2 and p3 give 12!
Advance BOTH
ugly[9] = 12 ✓
State: p2=6, p3=4, p5=2
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
ugly = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
10th ugly number: ugly[9] = 12 ✓
Key Insights:
✓ Each pointer generates a sequence
✓ Always pick minimum of three
✓ Advance pointer(s) that gave minimum
✓ Automatically handles duplicates!
✓ No heap needed, no HashSet needed!
✓ O(n) time, O(n) space - OPTIMAL!
Implementation
/**
* Three Pointers DP (Optimal)
* Time: O(n)
* Space: O(n)
*/
class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[n];
ugly[0] = 1;
// Three pointers
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
// Calculate next candidates
int next2 = ugly[p2] * 2;
int next3 = ugly[p3] * 3;
int next5 = ugly[p5] * 5;
// Pick minimum
int nextUgly = Math.min(next2, Math.min(next3, next5));
ugly[i] = nextUgly;
// Advance pointer(s) that gave minimum
// This handles duplicates automatically!
if (nextUgly == next2) p2++;
if (nextUgly == next3) p3++;
if (nextUgly == next5) p5++;
}
return ugly[n - 1];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.nthUglyNumber(10)); // 12
System.out.println(sol.nthUglyNumber(1)); // 1
}
}
⏰ Time: O(n) - Single pass through array
💾 Space: O(n) - Array storage only
Why This is Optimal:
✓ O(n) time - can't do better (must generate n numbers)
✓ O(n) space - minimal (just the result array)
✓ No heap overhead
✓ No HashSet overhead
✓ Automatically handles duplicates
✓ Simple, elegant code
✓ Perfect for interviews!
📊 Approach Comparison - The Complete Growth Journey
┌──────────────┬─────────────┬──────────┬──────────────────────┐
│ Approach │ Time │ Space │ Key Insight │
├──────────────┼─────────────┼──────────┼──────────────────────┤
│ Brute Force │ O(n×log m) │ O(1) │ Check each number │
│ Min-Heap │ O(n log n) │ O(n) │ Generate only ugly │
│ Three Ptr DP │ O(n) │ O(n) │ Track 3 sequences │
└──────────────┴─────────────┴──────────┴──────────────────────┘
THE COMPLETE LEARNING PROGRESSION:
Level 1: Brute Force
Thought: "Check 1, 2, 3, 4... until count = n"
Works? YES ✓
Optimal? NO ✗
Problem: Checks many non-ugly numbers
For n=1690: Checks ~850 MILLION numbers! 😱
Level 2: Optimization Insight #1
Question: "Why check non-ugly numbers?"
Realization: "Every ugly = prev ugly × {2,3,5}"
Idea: "GENERATE only ugly numbers!"
Level 3: Min-Heap Solution
Implementation: Use heap + HashSet
Result: O(n log n), O(n) space
Better: Only generates ugly numbers! ✓
But: Heap overhead, duplicates need HashSet
Level 4: Optimization Insight #2
Question: "Can I avoid duplicates?"
Realization: "Track THREE sequences!"
Idea: "Use pointers, pick minimum!"
Level 5: Three Pointers DP
Implementation: Array + 3 pointers
Result: O(n) time, O(n) space
Perfect: Optimal complexity, simple code! ✓
Growth: Learned DP pattern! 🌟
CONCRETE EXAMPLE (n=1690):
Brute Force:
Check ~850,000,000 numbers
Each check: O(log m) divisions
Total: BILLIONS of operations! 😱
Min-Heap:
Generate 1690 numbers
Each: O(log 1690) ≈ 10 heap ops
Total: ~17,000 operations
500,000x FASTER! 🚀
Three Pointers:
Generate 1690 numbers
Each: 3 comparisons + 1-3 increments
Total: ~6,700 operations
2.5x better than heap! ✨
💡 Key Learnings - Your Complete Growth
WHAT YOU LEARNED:
1. BRUTE FORCE FIRST:
✓ Natural: "Check each number"
✓ Simple: Easy to code and verify
✓ Valid: Correct but slow
✓ Foundation: Build from here!
2. FIRST OPTIMIZATION (Generation):
✓ Insight: "Don't check non-ugly!"
✓ Strategy: "Generate only ugly"
✓ Tool: Min-heap for smallest
✓ Improvement: O(n×log m) → O(n log n)
3. SECOND OPTIMIZATION (DP):
✓ Insight: "Avoid duplicates!"
✓ Strategy: "Track three sequences"
✓ Tool: Three pointers
✓ Improvement: O(n log n) → O(n)
✓ Learned: DP pattern with pointers!
4. PATTERN RECOGNITION:
✓ Multiple sequences merging
✓ Pick minimum from candidates
✓ Advance pointer(s) that gave min
✓ This is a COMMON DP pattern!
INTERVIEW STRATEGY:
Progressive Presentation:
"I can start by checking each number, but that's slow.
Better: Generate only ugly numbers.
Each ugly = previous × {2,3,5}.
Use min-heap to get smallest.
Time: O(n log n), Space: O(n).
Optimal: Track three sequences with pointers.
Always pick minimum of three.
Advance pointer(s) that gave minimum.
Time: O(n), Space: O(n).
Let me implement the DP solution."
Shows:
✓ Problem-solving progression
✓ Optimization thinking
✓ Understanding of trade-offs
✓ Knowledge of optimal solution
This is REAL growth! 🌱→🌳→🌲
⚠️ Common Mistakes
Mistake 1: Not handling duplicates in DP
// ❌ WRONG - Only advances one pointer
if (nextUgly == next2) p2++;
else if (nextUgly == next3) p3++;
else if (nextUgly == next5) p5++;
// ✓ CORRECT - Advances ALL that match
if (nextUgly == next2) p2++;
if (nextUgly == next3) p3++;
if (nextUgly == next5) p5++;
Mistake 2: Using int instead of long in heap
// ❌ WRONG - Overflow for large ugly numbers
PriorityQueue<Integer> heap = new PriorityQueue<>();
// ✓ CORRECT - Use long to avoid overflow
PriorityQueue<Long> heap = new PriorityQueue<>();
Mistake 3: Wrong initialization in DP
// ❌ WRONG - All pointers start at different positions
int p2 = 0, p3 = 1, p5 = 2;
// ✓ CORRECT - All start at 0 (pointing to 1)
int p2 = 0, p3 = 0, p5 = 0;
Mistake 4: Not checking for duplicates in heap approach
// ❌ WRONG - Adds duplicates to heap
for (int factor : new int[]{2, 3, 5}) {
heap.offer(ugly * factor);
}
// ✓ CORRECT - Use HashSet to track seen
if (!seen.contains(newUgly)) {
heap.offer(newUgly);
seen.add(newUgly);
}
🎯 Pattern Recognition
Problem Type: Sequence Generation with Multiple Sources
Core Pattern: Three Pointers / Multiple Sequence Merge
When to Apply:
✓ Generate sequence from multiple sources
✓ Need nth element in merged sequence
✓ Each source follows a pattern
✓ Must merge in sorted order
Recognition Keywords:
- "nth element"
- "prime factors limited to..."
- "generate sequence"
- "merge multiple sequences"
Similar Problems:
- Super Ugly Number (LC 313) - k factors instead of 3
- Merge K Sorted Lists (LC 23) - merge k sequences
- Kth Smallest in Multiplication Table (LC 668)
Key Components:
┌────────────────────────────────────────────┐
│ Multiple Sequences: ×2, ×3, ×5 │
│ Pointers: Track position in each │
│ Pick Minimum: Merge in order │
│ Advance: Pointer(s) that gave min │
│ DP Array: Store results │
└────────────────────────────────────────────┘
📝 Quick Revision Notes
🎯 Core Concept:
Generate nth ugly number (only factors 2,3,5). Brute force: Check each number O(n×log m). Better: Min-heap generates only ugly O(n log n). Optimal: Three pointers DP O(n) - maintain sequences ×2, ×3, ×5, always pick minimum, advance pointer(s) that gave min. Handles duplicates automatically!
⚡ Quick Implementations:
import java.util.HashSet;
import java.util.PriorityQueue;
public class Solution {
public int nthUglyNumber(int n) {
// First 15 ugly numbers:
// 1 = 1
// 2 = 2
// 3 = 3
// 4 = 2 × 2
// 5 = 5
// 6 = 2 × 3
// 8 = 2 × 2 × 2
// 9 = 3 × 3
// 10 = 2 × 5
// 12 = 2 × 2 × 3
// 15 = 3 × 5
// 16 = 2 × 2 × 2 × 2
// 18 = 2 × 3 × 3
// 20 = 2 × 2 × 5
// 24 = 2 × 2 × 2 × 3
// return naive(n);
// return minHeap(n);
return optimal(n);
}
private int optimal(int n) {
// step 1: base case
if (n == 1) {
return 1;
}
// step 2: maintain an ugly array
int[] ugly = new int[n];
ugly[0] = 1;
// step 3: we know that ugly numbers are generated by any one
// of earlier ugly numbers multiplied by 2 or 3 or 5
// step 4: lets maintain 3 pointers which are basically
// indices and are initially at 0. Multiply ugly[p2], ugly[p3]
// and ugly[p5] with 2, 3 and 5.
// For exmaple, ugly[1] = min(2,3,5).
int p2 = 0;
int p3 = 0;
int p5 = 0;
// step 5: calculate ugly array
for (int i = 1; i < n; i++) {
int ugly2 = ugly[p2] * 2;
int ugly3 = ugly[p3] * 3;
int ugly5 = ugly[p5] * 5;
// step 5: Whatever pointer contributed min out of (p2,p3,p5),
// increment that and repeat the same.
// step 6: Why that pointer increment?
// If we do not increment, we would be still getting 2 forever.
// Incrementing it would be providing 4 next time.
// Why other pointers not incremented?
// Still, 3 and 5 not added.
int newUgly = Math.min(ugly2, Math.min(ugly3, ugly5));
ugly[i] = newUgly;
// step 7: if both pointers are contributing minimu, increment both.
// This is another way to avoid duplicates
if (newUgly == ugly2) {
p2++;
}
if (newUgly == ugly3) {
p3++;
}
if (newUgly == ugly5) {
p5++;
}
}
return ugly[n - 1];
}
private int minHeap(int n) {
// step 1: base case
if (n == 1) {
return 1;
}
// step 2 - create a min heap with initial state and also visited set
PriorityQueue<Long> pq = new PriorityQueue<>();
pq.offer(1L);
HashSet<Long> visited = new HashSet<>();
// step 3: main concept is that an ugly number is always get derived
// from earlier ugly number multiplied by 2 or 3 or 5
// So, keep on generating the ugly numbers and push to queue till n.
// It will happen like [1,2,3,5,4,6,10,6,9,15,10,15,25]
// But we get correct result because we maintain visited set and min heap
for (int i = 2; i <= n; i++) {
long polled = pq.poll();
long newUgly = polled * 2;
if (!visited.contains(newUgly)) {
pq.offer(newUgly);
visited.add(newUgly);
}
newUgly = polled * 3;
if (!visited.contains(newUgly)) {
pq.offer(newUgly);
visited.add(newUgly);
}
newUgly = polled * 5;
if (!visited.contains(newUgly)) {
pq.offer(newUgly);
visited.add(newUgly);
}
}
long res = pq.poll();
return (int) res;
}
private int naive(int n) {
// step 1: base case
if (n == 1) {
return 1;
}
// step 2: 1 is always included as ugly number by default
// so start with 2 and count with 1 (as i is already counted)
int num = 2;
int count = 1;
while (count <= n) {
// step 3: check if existing number is ugly.
// Then only count it and if we got the nth num, return it.
if (isUgly(num)) {
count++;
}
if (count == n) {
break;
}
num++;
}
return num;
}
private boolean isUgly(int num) {
if (num <= 0) {
return false;
}
// prime factorization with 2, 3 and 5
while (num % 2 == 0) {
num = num / 2;
}
while (num % 3 == 0) {
num = num / 3;
}
while (num % 5 == 0) {
num = num / 5;
}
return num == 1;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.nthUglyNumber(1) == 1);
System.out.println(s.nthUglyNumber(2) == 2);
System.out.println(s.nthUglyNumber(3) == 3);
System.out.println(s.nthUglyNumber(10) == 12);
}
}
🔑 Key Insights:
- Natural Progression: Check all → Generate ugly → Three pointers
- First Insight: Every ugly = previous × {2,3,5}
- Second Insight: Track three sequences separately
- Three Pointers: p2, p3, p5 - all start at 0
- Pick Minimum:
Math.min(next2, Math.min(next3, next5)) - Advance All Matches: Handles duplicates (6 from both 2×3 and 3×2)
- Growth: O(n×log m) → O(n log n) → O(n)! ✓
🎪 Memory Aid:
"Three sequences: ×2, ×3, ×5!"
"Pick minimum, advance pointer(s)!"
"This is DP with pointers - brilliant!" ✨
🧪 Edge Cases
Case 1: n = 1
Input: n = 1
Output: 1
First ugly number is 1
Case 2: Small n
Input: n = 10
Output: 12
[1,2,3,4,5,6,8,9,10,12]
Case 3: Large n
Input: n = 1690
Output: 2123366400
DP handles efficiently!
All handled correctly! ✓
🎓 Complexity Analysis
Approach 1: Brute Force
Time: O(n × log m)
Check n ugly numbers
Each check: O(log m) divisions
m = nth ugly number (can be huge!)
Space: O(1)
Approach 2: Min-Heap
Time: O(n log n)
n iterations
Each: poll O(log n) + 3 offers O(log n)
Space: O(n)
Heap + HashSet
Approach 3: Three Pointers DP
Time: O(n)
Single pass
Each iteration: O(1) operations
Space: O(n)
Array storage only
Optimal! Can't do better than O(n)!
Happy practicing! 🎯
Note: This problem is a MASTERCLASS in optimization! You naturally start with brute force (check all), realize you can generate only ugly numbers (min-heap), then discover an even better way (three pointers DP). Each step builds on the previous insight. The three pointers pattern is BEAUTIFUL - it tracks three sequences, picks minimum, and handles duplicates automatically. This progression from O(n×log m) → O(n log n) → O(n) teaches you how to THINK about optimizations, not just memorize solutions. The DP pattern here (multiple pointers merging sequences) appears in many problems! True learning! 💪✨🌟