Easy Heap & DP Solution | Beats 100%
Heap Method\nPython []\nclass Solution(object):\n    def nthUglyNumber(self, n):\n        primes = [2,3,5]\n        uglyHeap = [1]\n        visited = set()\n   
# Heap Method\n```Python []\nclass Solution(object):\n    def nthUglyNumber(self, n):\n        primes = [2,3,5]\n        uglyHeap = [1]\n        visited = set()\n        visited.add(1)\n        for _ in range(n):\n            curr = heappop(uglyHeap)\n            for prime in primes:\n                new_ugly = curr * prime\n                if new_ugly not in visited:\n                    heappush(uglyHeap, new_ugly)\n                    visited.add(new_ugly)\n        return curr\n```\n```C++ []\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        vector<int> primes = {2, 3, 5};\n        priority_queue<long, vector<long>, greater<long>> uglyHeap;\n        unordered_set<long> visited;\n        \n        uglyHeap.push(1);\n        visited.insert(1);\n        \n        long curr;\n        for (int i = 0; i < n; ++i) {\n            curr = uglyHeap.top();\n            uglyHeap.pop();\n            for (int prime : primes) {\n                long new_ugly = curr * prime;\n                if (visited.find(new_ugly) == visited.end()) {\n                    uglyHeap.push(new_ugly);\n                    visited.insert(new_ugly);\n                }\n            }\n        }\n        return (int)curr;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int nthUglyNumber(int n) {\n        int[] primes = {2, 3, 5};\n        PriorityQueue<Long> uglyHeap = new PriorityQueue<>();\n        HashSet<Long> visited = new HashSet<>();\n        \n        uglyHeap.add(1L);\n        visited.add(1L);\n        \n        long curr = 1L;\n        for (int i = 0; i < n; i++) {\n            curr = uglyHeap.poll();\n            for (int prime : primes) {\n                long new_ugly = curr * prime;\n                if (!visited.contains(new_ugly)) {\n                    uglyHeap.add(new_ugly);\n                    visited.add(new_ugly);\n                }\n            }\n        }\n        return (int)curr;\n    }\n}\n```\n\n# DP\n```Python []\nclass Solution(object):\n    def nthUglyNumber(self, n):\n        primes = [2, 3, 5]\n        next_ugly = [2, 3, 5]\n        increase = [1, 1, 1]\n        arr = [1]\n        \n        for _ in range(1, n):\n            smallest = min(next_ugly)\n            arr.append(smallest)\n            \n            for i in range(3):\n                if next_ugly[i] == smallest:\n                    increase[i] += 1\n                    next_ugly[i] = primes[i] * arr[increase[i] - 1]\n        \n        return arr[-1]\n```\n```C++ []\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        vector<int> primes = {2, 3, 5};  // Initialize the primes array\n        vector<int> indices = {0, 0, 0}; // Initialize indices for multiples of 2, 3, 5\n        vector<int> uglyArr(1, 1);       // Initialize the ugly number array with 1\n\n        for (int i = 1; i < n; ++i) {\n            // Calculate the next possible ugly numbers\n            vector<int> next_uglies = {\n                uglyArr[indices[0]] * primes[0],\n                uglyArr[indices[1]] * primes[1],\n                uglyArr[indices[2]] * primes[2]\n            };\n            int min_value = *min_element(next_uglies.begin(), next_uglies.end()); // Find the smallest value\n            uglyArr.push_back(min_value); // Append the smallest value to uglyArr\n\n            // Update indices for primes that generated the current min_value\n            for (int j = 0; j < 3; ++j) {\n                if (next_uglies[j] == min_value) {\n                    ++indices[j];\n                }\n            }\n        }\n\n        return uglyArr[n - 1];\n    }\n};\n```\n```Java []\nclass Solution {\n    public int nthUglyNumber(int n) {\n        int[] primes = {2, 3, 5};  // Initialize the primes array\n        int[] indices = {0, 0, 0}; // Initialize indices for multiples of 2, 3, 5\n        List<Integer> uglyArr = new ArrayList<>();  // Initialize the ugly number array with 1\n        uglyArr.add(1);\n\n        for (int i = 1; i < n; ++i) {\n            // Calculate the next possible ugly numbers\n            int[] nextUglies = {\n                uglyArr.get(indices[0]) * primes[0],\n                uglyArr.get(indices[1]) * primes[1],\n                uglyArr.get(indices[2]) * primes[2]\n            };\n            int minValue = Math.min(nextUglies[0], Math.min(nextUglies[1], nextUglies[2]));  // Find the smallest value\n            uglyArr.add(minValue);  // Append the smallest value to uglyArr\n\n            // Update indices for primes that generated the current min_value\n            for (int j = 0; j < 3; ++j) {\n                if (nextUglies[j] == minValue) {\n                    indices[j]++;\n                }\n            }\n        }\n\n        return uglyArr.get(n - 1);\n    }\n}\n```\n\n![unnamed.jpg](https://assets.leetcode.com/users/images/197223e1-5228-4ffb-b894-57990b14588a_1723941550.9373198.jpeg)\n
['Hash Table', 'Math', 'Dynamic Programming', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Python3']