NeetCode #689LC-264Medium1-D Dynamic Programming
← Back to All Problems#689 · #264 · Ugly Number II(丑数 II)
📌 Problem Statement & Constraints
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given
n, return the n-th ugly number. Constraints: 1 <= n <= 1690.💡 Core Algorithmic Approaches
- Every ugly number has the form
2^a * 3^b * 5^c, so the sequence can be generated in increasing order. - Maintain the sequence
dpplus three pointersp2,p3,p5, each pointing at the next factor to multiply. - The next ugly number is
min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5), and every pointer whose product equals it advances. - Advancing all matching pointers at once avoids duplicate entries.
💻 Benchmark Python3 Implementation
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [1] * n
p2 = p3 = p5 = 0
for i in range(1, n):
nxt = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
dp[i] = nxt
if nxt == dp[p2] * 2:
p2 += 1
if nxt == dp[p3] * 3:
p3 += 1
if nxt == dp[p5] * 5:
p5 += 1
return dp[n - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with three pointers.
💾 Space Complexity
O(n): the generated sequence.
⚠️ Interview Pitfalls & Follow-ups
- Advancing only one pointer: when the minimum is produced by several combinations (for example 6 = 2 x 3 = 3 x 2), every matching pointer must advance or duplicates appear.
- Using a heap without deduplication: a heap works but needs a
seenset; the three-pointer method is cleaner. - Starting
dp[0]at 0: the first ugly number is 1. - Testing primality directly: that is far too slow for n up to 1690 and misses the multiplicative structure.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.