264: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nWe will use a dynamic programming approach to solve this problem. We will
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe will use a dynamic programming approach to solve this problem. We will start with the first ugly number, which is 1, and then generate all the other ugly numbers. We will use three pointers to keep track of the next multiple of 2, 3, and 5 respectively. We will generate the next ugly number by selecting the minimum of the three next multiples, adding it to the list of ugly numbers, and updating the corresponding pointer. We will repeat this process until we have generated the nth ugly number.\n\nThe time complexity of this algorithm is O(n), and the space complexity is O(n) as we need to store the list of n ugly numbers.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        ugly = [1]  # initialize list of ugly numbers with 1\n        i2, i3, i5 = 0, 0, 0  # initialize pointers for next multiples of 2, 3, and 5 respectively\n        while len(ugly) < n:\n            # generate the next ugly number as the minimum of the next multiples of 2, 3, and 5\n            next_ugly = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)\n            # add the next ugly number to the list\n            ugly.append(next_ugly)\n            # update the corresponding pointer for the next multiple\n            if next_ugly == ugly[i2]*2:\n                i2 += 1\n            if next_ugly == ugly[i3]*3:\n                i3 += 1\n            if next_ugly == ugly[i5]*5:\n                i5 += 1\n        return ugly[-1]  # return the nth ugly number\n\n```
['Hash Table', 'Math', 'Dynamic Programming', 'Python', 'Python3']