Solution Explanation:

The problem asks to find the nth ugly number. An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

There are two main approaches to solve this problem:

Approach 1: Using a Heap (Priority Queue)

This approach leverages a min-heap to efficiently manage and retrieve the smallest ugly number at each step.

1. Initialization: Start with a min-heap containing the first ugly number, 1. A set vis is used to track already encountered ugly numbers, preventing duplicates.

2. Iteration: Iterate n times. In each iteration:

   • Extract the minimum element (ans) from the heap. This is the next ugly number.
   • Generate the next possible ugly numbers by multiplying ans with 2, 3, and 5.
   • If a generated number is not already in the vis set (meaning it's a new ugly number), add it to the heap and the vis set.

3. Result: After n iterations, the last extracted number (ans) is the nth ugly number.

Approach 2: Dynamic Programming

This approach uses dynamic programming to build up a list of ugly numbers.

1. Initialization: Create a DP array dp of size n to store the ugly numbers. Initialize dp[0] to 1. Initialize pointers p2, p3, and p5 to 0, which will track the indices of the next multiples of 2, 3, and 5 respectively within the dp array.

2. Iteration: Iterate from 1 to n-1. For each index i:

   • Calculate the next multiples of 2, 3, and 5 using the pointers: next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5.
   • Find the minimum among these three multiples; this is the next ugly number, dp[i].
   • Increment the pointers p2, p3, and p5 depending on which multiple was selected.

3. Result: dp[n-1] contains the nth ugly number.

Time Complexity Analysis:

Approach 1 (Heap):

• The heap operations (insertion and extraction) take O(log k) time, where k is the number of elements in the heap. In the worst case, k can be proportional to n, resulting in O(n log n) time complexity. However, the actual number of elements in the heap at any time is much smaller than n, because many numbers are already present in the vis set. Therefore, the amortized time complexity is closer to O(n).

Approach 2 (DP):

• The DP approach iterates through the DP array once, taking O(n) time. The operations within the loop are constant-time. Thus, the time complexity is O(n).

Space Complexity Analysis:

Approach 1 (Heap):

• The heap and the vis set store at most O(n) elements in the worst case.

Approach 2 (DP):

• The DP array dp uses O(n) space.

Code Examples (Python):

Approach 1 (Heap):

import heapq
 
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h = [1]
        vis = {1}
        ans = 1
        for _ in range(n):
            ans = heapq.heappop(h)
            for v in [2, 3, 5]:
                nxt = ans * v
                if nxt not in vis:
                    vis.add(nxt)
                    heapq.heappush(h, nxt)
        return ans

Approach 2 (DP):

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [1] * n
        p2 = p3 = p5 = 0
        for i in range(1, n):
            next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(next2, next3, next5)
            if dp[i] == next2:
                p2 += 1
            if dp[i] == next3:
                p3 += 1
            if dp[i] == next5:
                p5 += 1
        return dp[-1]

The DP approach is generally preferred due to its simpler implementation and slightly better time complexity in practice, although both approaches have linear time complexity in the asymptotic sense. The heap based approach might be preferable if you needed to quickly access other ugly numbers beyond the nth one without recomputing.