LeetCode 264 Ugly Number II - Two approaches(Med, Java, O(n))

Problem Overview

• LeetCode 264 Ugly Number II

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. The sequence starts: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Solution 1: Dynamic Programming with Three Pointers (Recommended)

This is the most efficient approach with O(n) time and O(n) space complexity.

Key Insight: Every ugly number (except 1) is formed by multiplying a smaller ugly number by 2, 3, or 5.

Algorithm:

1. Maintain three pointers (p2, p3, p5) that track positions in the ugly number array
2. At each step, calculate the next candidates by multiplying existing ugly numbers by 2, 3, and 5
3. Choose the minimum candidate as the next ugly number
4. Advance the corresponding pointer(s)

Why it works:

• next2 = arr[p2] * 2 gives the next ugly number in the "×2" sequence
• next3 = arr[p3] * 3 gives the next ugly number in the "×3" sequence
• next5 = arr[p5] * 5 gives the next ugly number in the "×5" sequence
• Taking the minimum ensures we get ugly numbers in ascending order

class Solution {
    public int nthUglyNumber(int n) {
       int arr[]=new int[n];
       arr[0]=1;
       int p2=0,p3=0,p5=0;
       for(int i=1;i<n;i++){
            int next2=arr[p2]*2;
            int next3=arr[p3]*3;
            int next5=arr[p5]*5;
            int nextugly=Math.min(next2,Math.min(next3, next5));
            arr[i]=nextugly;

            if (nextugly == next2) p2++;
            if (nextugly == next3) p3++;
            if (nextugly == next5) p5++;
       } 
       return arr[n-1];
    }
}

Important detail: The if statements use == (not else if) because multiple pointers might generate the same value (e.g., 2×3 = 3×2 = 6), and we need to advance all relevant pointers to avoid duplicates.

Solution 2: Min-Heap Approach

An alternative approach uses a min-heap to generate ugly numbers:

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        Set<Long> seen = new HashSet<>();
        int[] factors = {2, 3, 5};

        heap.offer(1L);
        seen.add(1L);

        long ugly = 1;
        for (int i = 0; i < n; i++) {
            ugly = heap.poll();
            for (int factor : factors) {
                long next = ugly * factor;
                if (!seen.contains(next)) {
                    heap.offer(next);
                    seen.add(next);
                }
            }
        }
        return (int) ugly;
    }
}

Time Complexity: O(n log n) due to heap operations Space Complexity: O(n) for heap and set

Comparison

The three-pointer approach is preferred for its optimal time complexity and clean implementation once you understand the logic.