Python | Dynamic Programming
see the Successfully Accepted Submission\n\n# Code\n\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        # Initialize the ugly number list wi
[see the Successfully Accepted Submission](https://leetcode.com/problems/ugly-number-ii/submissions/1359673517/?source=submission-ac)\n\n# Code\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        # Initialize the ugly number list with the first ugly number\n        ugly = [1]\n        \n        # Initialize pointers for multiples of 2, 3, and 5\n        i2 = i3 = i5 = 0\n        \n        # Continue generating ugly numbers until we reach the nth one\n        while len(ugly) < n:\n            # Calculate the next candidates for ugly numbers\n            next_ugly_2 = ugly[i2] * 2\n            next_ugly_3 = ugly[i3] * 3\n            next_ugly_5 = ugly[i5] * 5\n            \n            # Choose the smallest candidate\n            next_ugly = min(next_ugly_2, next_ugly_3, next_ugly_5)\n            ugly.append(next_ugly)\n            \n            # Increment the corresponding pointer(s)\n            if next_ugly == next_ugly_2:\n                i2 += 1\n            if next_ugly == next_ugly_3:\n                i3 += 1\n            if next_ugly == next_ugly_5:\n                i5 += 1\n        \n        # Return the nth ugly number\n        return ugly[n-1]\n\n```\n\n# Approach\n\n### Initialization:\n\n1. Start with the first ugly number, which is `1`.\n2. Use three pointers, `i2`, `i3`, and `i5`, to track the positions for multiples of `2`, `3`, and `5` respectively.\n3. The initial values of these pointers will all be `0`, meaning the smallest multiples of `2`, `3`, and `5` initially are `2*1`, `3*1`, and `5*1`.\n\n### Generate the sequence:\n\n1. For each subsequent ugly number, select the smallest value among `2 * ugly[i2]`, `3 * ugly[i3]`, and `5 * ugly[i5]`.\n2. Append this smallest value to the list of ugly numbers.\n3. Move the corresponding pointer (i.e., increment `i2`, `i3`, or `i5`) for the selected minimum value.\n4. Repeat the process until the nth ugly number is found.\n\n### Return the nth ugly number from the list.\n\n# Explanation\n\n- **Time Complexity:** The loop runs `n` times, and each step takes constant time, so the time complexity is `O(n)`.\n- **Space Complexity:** We store `n` ugly numbers in the list, so the space complexity is `O(n)`.\n\n# Example Run\n\nFor `n = 10`, the generated sequence is `[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]`, and the 10th ugly number is `12`.\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']