⚡Flashcard Drill➔
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

  1. Every ugly number has the form 2^a * 3^b * 5^c, so the sequence can be generated in increasing order.
  2. Maintain the sequence dp plus three pointers p2, p3, p5, each pointing at the next factor to multiply.
  3. The next ugly number is min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5), and every pointer whose product equals it advances.
  4. 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 seen set; 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems