Log inSign up
mediumLeetCodeNot Started

Ugly Number II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

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 n-th ugly number.

Note that 1 is typically treated as an ugly number.

Example 1 · Example 1: Tenth Ugly Number:

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. Min-Heap Generation State: (1) / \ (2) (3) / (5)

Example 2 · Example 2: First Ugly Number:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, so all prime factors are in {2, 3, 5}.

Constraints:

  • 1 <= n <= 1690

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand generation of numbers with prime factorization constraints.
  • Eliminate duplicate generation by advancing multiple pointers concurrently.
  • Compare Min-Heap generation with multi-pointer DP.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generate Nth number with restricted prime factors.
  • Each valid number is formed by multiplying an earlier valid number.
  • Three-pointer dynamic programming / Min-Heap sequence generation.

Algorithmic Decision Tree:

  • Testing integers sequentially is too slow (ugly numbers become sparse).
  • Min-Heap generates candidates in O(N log N).
  • Three Pointers DP achieves strict linear O(N) time and O(N) space.

Connected Patterns:

Super Ugly NumberFind K Pairs with Smallest Sums

1. Brute Force — Test Each Integer Sequentially

Intuition

Increment a counter from 1 upward. For each number, divide out 2, 3, and 5 as much as possible. If the remainder is 1, it is ugly. Stop when count reaches n.

When to apply: Only for understanding the problem definition (times out for n > 50).

Algorithm

  1. Step 1: Define isUgly(num): divide num by 2, 3, 5 while divisible. Return num == 1.
  2. Step 2: Loop num = 1, 2, 3 ...
  3. Step 3: If isUgly(num), count++.
  4. Step 4: When count == n, return num.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2using namespace std;
3
4class Solution {
5 bool isUgly(int num) {
6 if (num <= 0) return false;
7 while (num % 2 == 0) num /= 2;
8 while (num % 3 == 0) num /= 3;
9 while (num % 5 == 0) num /= 5;
10 return num == 1;
11 }
12
13public:
14 int nthUglyNumber(int n) {
15 int count = 0;
16 int num = 0;
17 while (count < n) {
18 num++;
19 if (isUgly(num)) {
20 count++;
21 }
22 }
23 return num;
24 }
25};
26
27int main() {
28 Solution sol;
29 cout << "10th Ugly Number (Brute Force): " << sol.nthUglyNumber(10) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(U_n) — O(U_n) exponential runtime.
  • Space complexity: O(1) — O(1) auxiliary space.

Why Brute Force Doesn't Scale:

Testing sequentially takes 2 billion operations for n = 1690. Three Pointers DP takes exactly 1690 operations (1,000,000x faster).

Three Pointers DP computes the 1690th ugly number in ~0.05ms.

2. Better — Min-Heap with Visited Set

Intuition

A Min-Heap generates candidates in strictly ascending order. Push 1 into heap and visited set. In each step, pop the smallest element x. If this is the nth pop, return x. Otherwise push 2x, 3x, 5x if not already in visited set.

When to apply: When using standard heap-based sequence expansion.

Algorithm

  1. Step 1: Initialize Min-Heap with 1. Add 1 to visited set.
  2. Step 2: Loop n times: curr = heap.pop().
  3. Step 3: If on nth iteration: return curr.
  4. Step 4: For factor in [2, 3, 5]: nextVal = curr * factor; if unvisited, push and add to set.
  5. Step 5: Return curr.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8 int nthUglyNumber(int n) {
9 priority_queue<long long, vector<long long>, greater<long long>> minHeap;
10 unordered_set<long long> visited;
11
12 minHeap.push(1);
13 visited.insert(1);
14
15 long long curr = 1;
16 int factors[3] = {2, 3, 5};
17
18 for (int i = 0; i < n; i++) {
19 curr = minHeap.top();
20 minHeap.pop();
21
22 for (int f : factors) {
23 long long nextVal = curr * f;
24 if (!visited.count(nextVal)) {
25 visited.insert(nextVal);
26 minHeap.push(nextVal);
27 }
28 }
29 }
30 return (int)curr;
31 }
32};
33
34int main() {
35 Solution sol;
36 cout << "10th Ugly Number (Min-Heap): " << sol.nthUglyNumber(10) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) heap time.
  • Space complexity: O(N) — O(N) memory for heap and set.

3. Optimal — Three Pointers Dynamic Programming

Intuition

Maintain dp[0 ... n-1] with dp[0] = 1. Maintain p2 = 0, p3 = 0, p5 = 0. For each i from 1 to n-1: candidate2 = dp[p2]*2, candidate3 = dp[p3]*3, candidate5 = dp[p5]*5. Set dp[i] = min(candidate2, candidate3, candidate5). Increment any pointer whose candidate equals dp[i] (deduplicating ties like 6). Return dp[n-1].

When to apply: Standard optimal solution achieving linear O(N) runtime and O(N) memory.

Algorithm

  1. Step 1: Allocate dp array of size n with dp[0] = 1.
  2. Step 2: Initialize p2 = 0, p3 = 0, p5 = 0.
  3. Step 3: Loop i from 1 to n - 1:
  4. Step 4: next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5.
  5. Step 5: dp[i] = min(next2, min(next3, next5)).
  6. Step 6: If dp[i] == next2: p2++.
  7. Step 7: If dp[i] == next3: p3++.
  8. Step 8: If dp[i] == next5: p5++.
  9. Step 9: Return dp[n - 1].

Interactive Trace for Ugly Number II

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: dp[0] = 1, p2=0, p3=0, p5=0
Visual state
Values and pointers at this exact step
tree
dp[0]: 1
1
dp[1]: 2
2
Cand: 3
3
Cand: 5
5

Node order shown; add connections to display explicit tree edges.

p2: u1
Check / comparison
dp[1] = 2. Advance p2 to 1.
Decision / next transition
Ugly numbers so far: [1, 2].
Why this step matters

Step 1: dp[0] = 1, p2=0, p3=0, p5=0. Next candidates: 1*2=2, 1*3=3, 1*5=5. Min is 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int nthUglyNumber(int n) {
9 vector<int> dp(n);
10 dp[0] = 1;
11 int p2 = 0, p3 = 0, p5 = 0;
12
13 for (int i = 1; i < n; i++) {
14 int next2 = dp[p2] * 2;
15 int next3 = dp[p3] * 3;
16 int next5 = dp[p5] * 5;
17
18 int nextUgly = min({next2, next3, next5});
19 dp[i] = nextUgly;
20
21 if (nextUgly == next2) p2++;
22 if (nextUgly == next3) p3++;
23 if (nextUgly == next5) p5++;
24 }
25 return dp[n - 1];
26 }
27};
28
29int main() {
30 Solution sol;
31 cout << "10th Ugly Number (Optimal DP): " << sol.nthUglyNumber(10) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — O(N) linear time.
  • Space complexity: O(N) — O(N) DP table memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Test Every Integer SequentiallyO(U_n)O(1)Check integers 1, 2, 3, ... by repeatedly dividing by 2, 3, and 5 until n ugly numbers are found.Testing over 2 billion non-ugly numbers.
2.Better — Min-Heap with Visited SetO(N log N)O(N)Start with 1 in Min-Heap. In each step, pop min x and push 2x, 3x, 5x (checking visited set). Repeat n times.Heap operations.
3.Optimal — Three Pointers Dynamic ProgrammingOptimalO(N)O(N)Maintain array dp[n] and pointers p2, p3, p5. dp[i] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5). Advance matching pointers.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Using if-else instead of independent ifs

If nextUgly == 6, both p2 and p3 must increment. An if-else will only increment one, causing 6 to be added twice.

Integer overflow in Min-Heap approach

When generating products like curr * 5, intermediate values can exceed 231 - 1; use 64-bit integer (long long) for heap approach.

Starting from 0 instead of 1

Ugly numbers are strictly positive integers.

Crucial Edge Cases to Validate:

  • n == 1 — Returns 1.
  • n == 1690 — Fits within standard 32-bit signed integer (2,123,366,400 < 231 - 1).
  • Multiple factor match (e.g. 6 = 2*3 = 3*2) — Non-exclusive if checks advance both p2 and p3 simultaneously, preventing duplicate 6.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out that the problem can be framed as merging three sorted streams (multiples of 2, 3, and 5).
  2. Highlight the multiple pointer increment pattern to eliminate duplicates.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must we use separate if statements (rather than if-else) to increment p2, p3, and p5?

Back to DSA Sheet