Leetcode Daily Question 18/08/2024 - 264. Ugly Number II

Problem Description:

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the nth ugly number.

#dp apprach
class Solution:
  def nthUgly(self, n: int) -> int:
    dp = [0] * n
    dp[0] = 1
    next_2 = 2
    next_3 = 3
    next_5 = 5
    i = j = k = 0
    for a in range(1,n):
      next_ugly = min(next_2, next_3, next_5)
      dp[a] = next_ugly
      
      if next_ugly == next_2:
        i += 1
        next_2 = dp[i] * 2
      if next_ugly == next_3:
        j += 1
        next_3 = dp[j] * 3
      if next_ugly == next_5:
        k += 1
        next_5 = dp[k] * 5
   	return dp[-1]
  

# min heap approach
import heapq
class Solution:
  def nthUgly(self, n: int) -> int:
    min_heap = [1]
    seen = {1}
    ugly = 1
    factors = [2,3,5]
    for _ in range(n):
      ugly = heapq.heappop(min_heap)
      for factor in factors:
        new_ugly = ugly * factor
        if new_ugly not in seen:
          seen.add(new_ugly)
          heapq.heappush(min_heap, new_ulgy)
    return ugly

Explanation:

To solve this problem, we need to find a way to generate new ugly numbers from existing ones. Combined with memorisation, we can create an efficient solution.

We shall present 2 solutions, one with dp and another with min heap.

Let's start with dp. We initiate dp of size n, representing the n ugly numbers. The first ugly number is 1 by default.

We keep track of the next multiple of 2, 3, and 5 and their indices. The next ugly number then must be the minimum of the next multiple of 2,3, and 5.

Once we decided what the new ugly number is, we increment the index associated with the next multiple, and generate the next possible multiple using previously generated ugly number.

def nthUgly(n):
  dp = [0] * n
  dp[0] = 1
  next_2 = 2 # we started with 1, so next multple of 2 is 1 * 2 = 2
  next_3 = 3 # similarly, next mutliple of 3 is 1 * 3 = 3
  next_5 = 5 # next multiple of 5 is 1 * 5 = 5
  i = j = k = 0 # indices tracking the next mutlples. 
  for a in range(1,n): # we already have dp[0] = 1
    new_ulgy = min(next_2,next_3,next5)
    dp[a] = new_ugly
    
    if new_ugly == next_2:
      i += 1
      next_2 = dp[i] * 2 # if new_ulgy is next_2 we generate the next multiple of 2 using next_2.
    if new_ugly == next_3:
      j += 1
      next_3 = dp[j] * 3
    if new_ugly == next_5:
      k += 1
      next_5 = dp[k] * 5
  
  return dp[-1]

This solution gives a time complexity of O(n) as we need to generate ugly numbers up to n. Space complexity of O(n) as we need to store them in memory.

Another approach we could do is using a min heap. The min heap makes sure that the next ugly number is always first to be popped.

We use a seen set to keep track of seen ugly numbers and generate ugly numbers by multiplying 2, 3, or 5 to the current ugly number. If these are new ugly numbers that have not been seen we can add it to the heap.

The benefit of using a heap is that it keeps the ugly numbers ordered, so we do not have to track which multiple has been used.

import heapq
def nthUlgy(n):
  min_heap = [1]
  seen = {1}
  ugly = 1
  factors = [2,3,5]
  for _ in range(n):
    ulgy = heapq.heappop(min_heap)
    for factor in factors:
      new_ugly = ugly * factor
      if new_ugly not in seen:
        seen.add(new_ulgy)
        heapq.heappush(min_heap, new_ugly)
  return ugly

The deficit of using heap is the time complexity. Since each heap operation takes O(log n) time and we need to generate n ugly numbers, we have a time complexity of O(nlog n).

The space complexity remains the same as we memorises the first n ugly numbers (O(n)).

The two full solutions can be found near the top of the page.