Python O(n) DP solution using heap.
The idea is similar to leetcode problem: 23. Merge k Sorted Lists. You can think of each prime number is the head of a list that are multiplies of that prime. W
The idea is similar to leetcode problem: 23. Merge k Sorted Lists. You can think of each prime number is the head of a list that are multiplies of that prime. When insert into the heap, we need to both record the index of which prime, and the index on the dp array. Because the next multiplier will be the next index on the DP array.\n\nAlso use a hashset to avoid duplicated number gets into the DP array.\n\nThere will be only less than k = len(primes) nodes in the heap so push and pop operation will be O(logk), each number will be duplicated k times maximum. So the time complexity is O(knlogk), since k <= 100, so it is O(n). Space complexity is also O(n).\n\n```\nimport heapq\n\nclass Solution:\n    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n        dp, heap, visited = [1], [], set()\n        for i, p in enumerate(primes):\n            heapq.heappush(heap, (p, i, 0))\n        \n        while len(dp) < n:\n            val, prime_idx, dp_idx = heapq.heappop(heap)\n            if val not in visited:\n                dp.append(val)\n                visited.add(val)\n            heapq.heappush(heap, (primes[prime_idx] * dp[dp_idx + 1], prime_idx, dp_idx + 1))\n        \n        return dp[-1]\n```\n
['Heap (Priority Queue)', 'Python']