Best Python Solution | Most intuitive
\n\nMost intuitive and best heap solution you could ever get for this\n\nIdea is clear that we need a min heap to store ugly numbers and pop the smallest ugly n
![image](https://assets.leetcode.com/users/images/1b34f290-8e93-4e23-8212-78642fde1983_1661342958.5084677.png)\n\n**Most intuitive and best heap solution you could ever get for this**\n\nIdea is clear that we need a min heap to store ugly numbers and pop the smallest ugly number (say `x`) and corresponding to that there should be` 2*x`, `3*x`, ` 5*x` as possible candidates, so push them by ensuring they are not already present in the heap, this can be done with a dictionary (hashmap)   \n\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        h = [1]\n        d = {}\n        while n-1:\n            x = heapq.heappop(h)\n            if x*2 not in d:\n                heapq.heappush(h, x*2)\n                d[x*2] = 1\n            if x*3 not in d:\n                heapq.heappush(h, x*3)\n                d[x*3] = 1\n            if x*5 not in d:\n                heapq.heappush(h, x*5)\n                d[x*5] = 1\n            n -= 1\n        return heapq.heappop(h)\n```
['Heap (Priority Queue)', 'Python']