The O(n) Club: Ugly Numbers II – Three Pointers, Zero Ugly Bugs

The O(n) Club: Ugly Numbers II – Three Pointers, Zero Ugly Bugs

⚡ TL;DR

Ugly numbers are those rare creatures with only 2, 3, or 5 as their prime factors. The naive approach wastes your CPU and your patience. Be cool: use three pointers and dynamic programming.

// Java – Smooth and fast
public int nthUglyNumber(int n) {
    int[] dp = new int[n]; dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        int next = Math.min(dp[p2]*2, Math.min(dp[p3]*3, dp[p5]*5));
        dp[i] = next;
        if (next == dp[p2]*2) p2++;
        if (next == dp[p3]*3) p3++;
        if (next == dp[p5]*5) p5++;
    }
    return dp[n-1];
}

🧠 How Devs Usually Mess This Up

Classic rookie move: painstakingly check every number for ‘ugly-ness’ by prime factoring until your laptop fan sounds like a jet engine. Or, you forget that the sequence starts at ‘1’ (which, yes, is technically ugly). The worst? Advancing only one pointer when two or three are tied—congratulations, you just invented ugly duplicate bugs. We’ve all been there (usually right before an interview).

🔍 What’s Actually Going On

Think of the ugly number parade as a conveyor belt. Instead of grabbing every item off the warehouse floor (read: brute force), you only need to track three assembly lines: multiplying by 2, 3, and 5. At each step, pick the smallest ‘product’, add it to your visible sequence, and nudge any line that helped build it. That way, each new ugly number is born out of clean, orderly DP magic—not numerical chaos.

🛠️ PseudoCode

• Create a dp array length n. Set dp[0]=1 (yes, really, 1 counts).
• Start three pointers: p2=0, p3=0, p5=0.
• For each i from 1 to n-1:
  • Compute three candidates:
    next2 = dp[p2] * 2
next3 = dp[p3] * 3
next5 = dp[p5] * 5
  • Pick the minimum as dp[i].
  • If it matches next2, increment p2. Same for p3 and p5. Advance all that match to sidestep duplicates.
• Return dp[n-1]. Put your feet up.

💻 The Code

public int nthUglyNumber(int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        int next2 = dp[p2] * 2;
        int next3 = dp[p3] * 3;
        int next5 = dp[p5] * 5;
        int nextUgly = Math.min(next2, Math.min(next3, next5));
        dp[i] = nextUgly;
        if (nextUgly == next2) p2++;
        if (nextUgly == next3) p3++;
        if (nextUgly == next5) p5++;
    }
    return dp[n - 1];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• The ‘1’ problem: Forgetting to start with 1 ruins the entire sequence (and possibly your day).
• Missing the pointer party: If you don’t bump all pointers that share the same min, duplicates sneak in. Don’t let that happen on your watch.
• Brute force blues: Stepping through all numbers works only if you love slow heartbreak and O(n²) performance.
• The happy news: This approach is O(n) time, O(n) space—DP at its finest. Don’t overthink it with fancy heaps; the three-pointer parade is all you need.

🧠 Interviewer Brain-Tattoo

“If you solve Ugly Numbers with brute force, the code review committee cries. Three pointers, one O(n) DP. That’s the ugly truth.”