264.ugly-number-ii.md

264. Ugly Number II

Dynamic Programming

We have an array dp of first n ugly numbers, the first one is 1, that is dp[1] = 1.

Then dp[2] = min(2 * dp[1], 3 * dp[1], 5 * dp[1]) = 2, which is 2 * dp[1] so we move the pointer of 2 to 2.

Then dp[3] = min(2 * dp[2], 3 * dp[1], 5 * dp[1]) = 3, which is 3 * dp[1] so we move the pointer of 3 to 2. And so on.

But we need to handle the duplicate number generated from some pointers, for example, 6 = 2×3 = 3×2, so we have to move the pointers forward both. All matching candidates must advance, to avoid duplicate values.

Generaly speaking, the next number has to be the smallest number among all the existing numbers multiplied by 2, 3, 5 and hasn't been generated before. But we can't generate all possible number which grows much faster. Hence, we only generate from the previous smallest number only every time.

dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
// p2, p3, p5 are the pointers for 2, 3, 5 respectively.

---

What's the next number? It would be the smallest number all the previously existing ugly numbers multiplied by 2 or 3, 5 that hasn't shown before.

We start calculating from 1, the next number is min(2 * 1, 3 * 1, 5 * 1) that hasn't shown, that is 2, and you can think that is dp[n = 2] which comes from min(2 * dp[n = 1], 3 * dp[1], 5 * dp[1]).

Then, what's the next number? Now we only need to consider min(2 * 2, 3 * 1, 5 * 1), that would be min(2 * dp[2], 3 * dp[1], 5 * dp[1]), that means we have three pointers (for 2, 3, 5 respectively) points to the previous existing number, then we move the pointer if we use that in the round.

dp[1] = 1
p2 = p3 = p5 = 1

dp[2]: min(1×2, 1×3, 1×5) = 2 → dp = [1, 2], p2++
dp[3]: min(2×2, 1×3, 1×5) = 3 → dp = [1, 2, 3], p3++
dp[4]: min(2×2, 3×1, 1×5) = 4 → dp = [1, 2, 3, 4], p2++
dp[5]: min(3×2, 3×3, 1×5) = 5 → dp = [1, 2, 3, 4, 5], p5++
dp[6]: min(3×2, 3×3, 2×5) = 6 → dp = [1, 2, 3, 4, 5, 6], p2++, p3++ // Key point to handle the duplicate number
dp[7]: min(4×2, 3×3, 2×5) = 8 → dp = [1, 2, 3, 4, 5, 6, 8], p2++
// ... so on.

The wrong way to think this problem is that we just maintain the three pointers and move them to the next when selecting it, and we can get the result. But the correct way is that we need to consider the next number from the previous existing numbers, and we need to maintain the three pointers to point to the previous existing number.

n=1, 1
n=2, min(2 * 1, 3 * 1, 5 * 1) = 2
n=3, min(2 * 2, 3 * 1, 5 * 1) = 3
n=4, min(2 * 2, 3 * 2, 5 * 1) = 4
n=5, min(2 * 3, 3 * 2, 5 * 1) = 5
n=6, min(2 * 3, 3 * 2, 5 * 2) = 6
        // Which one to select?
n=7, min(2 * 4, 3 * 2, 5 * 2) = 6 // select 2 * 3, wrong answer
         ^^^^^

n=7, min(2 * 3, 3 * 3, 5 * 2) = 9 // select 3 * 2, wrong answer
                ^^^^^

Another way to think is using the idea of merge sort, assume we have three ugly number arrays, which are multiples of 2, 3, 5 respectively, and we merge them into one sorted array.

[1, 2, 4, 6, 8, 10, 12, 16, ...]
[1, 3, 6, 9, 12, 15, 18, 24, ...]
[1, 5, 10, 15, 20, 25, 30, ...]

Each prime has its own “merge stream”:

2 × [ugly[0], ugly[1], ...]
3 × [ugly[0], ugly[1], ...]
5 × [ugly[0], ugly[1], ...]

// 2, 3, 5 * [existing ugly numbers]
2 * [1, 2, 3, 4, 5, 6, 8, ...]
3 * [1, 2, 3, 4, 5, 6, 8, ...]
5 * [1, 2, 3, 4, 5, 6, 8, ...]

Each pointer tracks the smallest candidate that hasn't been used yet.

-Nice explanation

fun nthUglyNumber(n: Int): Int {
    if (n == 1) return n
    val dp = IntArray(n + 1)
    dp[1] = 1
    
    // Pointers for 2, 3, 5
    var p2 = 1
    var p3 = 1
    var p5 = 1
    for (i in 2..n) {
        val num2 = dp[p2] * 2
        val num3 = dp[p3] * 3
        val num5 = dp[p5] * 5
        
        dp[i] = minOf(num2, minOf(num3, num5))
        
        // Determine where does dp[i] come from and increment the 
        // pointer, please note that we will move all the pointers 
        // forward if we have multiple choices.
        // That's why we use `if` instead of `else if` here.
        if (dp[i] == num2) p2++
        if (dp[i] == num3) p3++
        if (dp[i] == num5) p5++
    }
    
    return dp[n]
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Heap

We maintain a min heap and add 2x, 3x and 5x into heap (make sure avoiding duplicate), the result will be the peek.

fun nthUglyNumber(n: Int): Int {
    val factors = listOf(2L, 3L, 5L)
    val minHeap = PriorityQueue<Long>()
    val seen = hashSetOf<Long>()
    var number = 1L
    minHeap.add(number)
    seen.add(number)
    for (i in 0 until n) {
        number = minHeap.poll()
        factors.forEach { factor ->
            val next = factor * number
            if (!seen.contains(next)) {
                minHeap.add(next)
                seen.add(next)
            }
        }
    }
    return number.toInt()
}

• Time Complexity: O(n * lg n).
• Space Complexity: O(n).