264. Ugly Number II

Hash Table Math Dynamic Programming Heap (Priority Queue)

Time: O(n)

Space: O(n)

Intuition

Generate ugly numbers in order using three pointers, each tracking which ugly number to multiply by 2, 3, or 5 next. Always pick the minimum of the three next candidates and advance the corresponding pointer(s).

Algorithm

1dp[1] = 1. p2 = p3 = p5 = 0.
2For i from 1 to n-1: next = min(dp[p2]*2, dp[p3]*3, dp[p5]*5).
3dp[i] = next. If dp[p2]*2 == next, p2++. If dp[p3]*3 == next, p3++. If dp[p5]*5 == next, p5++.
4Return dp[n-1].

Example Walkthrough

Input: n = 10

1.Sequence: 1,2,3,4,5,6,8,9,10,12. 10th = 12.

Output: 12

Common Pitfalls

•Advance ALL pointers that produced the minimum to avoid duplicates (e.g., 2*3=6=3*2 must advance both p2 and p3).

264.cs

// Approach: Three-pointer DP — track the next multiple of 2, 3, and 5 from
// the generated list; advance the pointer(s) that produced the minimum.
// Time: O(n) Space: O(n)

public class Solution
{
    public int NthUglyNumber(int n)
    {
        List<int> uglyNums = new List<int>();
        uglyNums.Add(1);
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;

        while (uglyNums.Count < n)
        {
            int next2 = uglyNums[i2] * 2;
            int next3 = uglyNums[i3] * 3;
            int next5 = uglyNums[i5] * 5;
            int next = Math.Min(next2, Math.Min(next3, next5));
            if (next == next2)
                i2++;
            if (next == next3)
                i3++;
            if (next == next5)
                i5++;
            uglyNums.Add(next);
        }

        return uglyNums[uglyNums.Count - 1];
    }
}

Was this solution helpful?