# My python solution is TLE, can anyone help?

• ``````def nthSuperUglyNumber(n, primes):
length = len (primes)
index = [0] * length
result = [1]
for t in range (n-1):
minNum = min([primes[i] * result[index[i]] for i in range(length)])
result.append(minNum)
for i in range(length):
if primes[i]*result[index[i]] == minNum:
index[i] +=1
return result[-1]
``````

I try the same thing in Java, and that is AC.

• you need to use a heap for getting the minNum. And you update on the index[i] numbers is taking O(k) time for each step.

Below is my unpolished code, 792 ms. It is not very brief or fast, but makes some of these points. I used frontier as your index, and frontierSet to store current values in frontier, so checking repeated number is each O(1) for each check (though you may need to do multiple times for each update).

``````class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""

uglies=[1]
frontier=[]
frontierSet=set()
for p in primes:
heappush(frontier, (p, p, 0)) # the result number, the prime number, and the index of basis.  (uglies[basis]*prime=result)

i=1
while i<n:
p=heappop(frontier)
frontierSet.remove(p[0])

uglies.append(p[0])

newBasis=p[2]+1
while p[1]*uglies[newBasis] in frontierSet:
newBasis+=1

heappush(frontier,((p[1]*uglies[newBasis], p[1],newBasis)))