What is the brute force approach and complexity for Ugly Number II?

Check each integer for factors other than 2, 3 and 5 until n ugly numbers are found with time complexity O(X log X) and space complexity O(1).

What is the optimal approach and complexity for Ugly Number II?

The next ugly number is the smallest of three next products; move every pointer that produced it with optimal time complexity O(n) and space complexity O(n).

How do you identify the pattern for Ugly Number II?

Look for key signals in the prompt: "n-th number whose only prime factors are 2, 3 and 5" indicates The numbers come in increasing order, so build them in order instead of testing each integer.; "every ugly number is 2, 3 or 5 times an earlier one" indicates Each new candidate is a product of an earlier ugly number, so there are three sorted streams to merge.; "6 = 2 × 3 = 3 × 2" indicates The same value can come from two streams. It must be counted once, so every stream that produced it advances..

Ugly Number II

Medium·LeetCode #264 Pro OnlyPattern Transfer

LeetCode

Problem Statement

An ugly number is a positive integer whose only prime factors are 2, 3 and 5. The number 1 counts as ugly.

Given n, return the n-th ugly number when the ugly numbers are listed in increasing order.

Input

n: a positive integer.

Output

The n-th ugly number, as an int.

Example 1

Input: n = 10

Output: 12

The first ten ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

Example 2

Input: n = 1

Output: 1

The first ugly number is 1.

Constraints

• 1 ≤ n ≤ 1690

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“n-th number whose only prime factors are 2, 3 and 5”

→ The numbers come in increasing order, so build them in order instead of testing each integer.

“every ugly number is 2, 3 or 5 times an earlier one”

→ Each new candidate is a product of an earlier ugly number, so there are three sorted streams to merge.

“6 = 2 × 3 = 3 × 2”

→ The same value can come from two streams. It must be counted once, so every stream that produced it advances.

Approach Complexity Ladder

Brute Force — test every numberO(X log X)O(1)

Check each integer for factors other than 2, 3 and 5 until n ugly numbers are found

Better — min-heap of candidates and a setO(n log n)O(n)

Pop the smallest candidate n times; push its × 2, × 3 and × 5 unless already seen

Optimal — three pointers over three sorted streamsO(n)O(n)

The next ugly number is the smallest of three next products; move every pointer that produced it

Brute Force Intuition

Count upward from 1. A number is ugly if dividing out every 2, 3 and 5 leaves 1. Keep counting ugly numbers until there are n of them.

Recognition rule for this sub-pattern:

Push the head of each list; pop the smallest, push its successor.

Remember this · K-way Merge

Trigger

K sorted lists/arrays, kth smallest across sorted rows, smallest range covering all lists.

Think

The next smallest item overall must be the front of some list — which one?

Key question

What do I push back into the heap after popping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture