# Heap solution would be TLE

• As this is an extension of problem 264. Ugly Number II, we could just generalise from it.

While, in my opinion, the hard (weird) part is that I've got several TLEs.

#### Plain O(nk) solution

TLE version

``````  # Plain O(n*k)
def nth_super_ugly_number(n, primes)
numbers = [1]

# TLE by this (expensive) hash
primes_and_ids = primes.reduce({}){|ha, prime| ha[prime] = 0; ha }

(n-1).times do
candidates = primes_and_ids.map{|prime, id| [ prime, prime * numbers[id] ]}
min = candidates.map(&:last).min

candidates.each do |prime, candidate|
next unless candidate == min
primes_and_ids[prime] += 1
end

numbers << min
end

numbers[n-1]
end

``````

I used a hash above, which might be a little expensive with massive inputs. So I replaced it with an array. Got passed.

``````  # Plain O(n*k)
def nth_super_ugly_number(n, primes)
numbers = [1]

idx = [0]*primes.count

(n-1).times do
min = primes.map.with_index{|prime, i| prime * numbers[ idx[i] ] }.min

primes.each_with_index do |prime, i|
next unless min == prime * numbers[ idx[i] ]
idx[i] += 1
end

numbers << min
end

numbers[n-1]
end
``````

#### Heap Solution (TLE)

Using a Priority Queue (a minimum heap) aims to improves this linear searching code:

``````min = primes.map.with_index{|prime, i| prime * numbers[ idx[i] ] }.min
``````

While, just as vcoderld said in Java three methods, 23ms, 36 ms, 58ms(with heap), performance explained

Besides, the remain part (the inner loop) takes complexity between Nlog(K) and NKlog(K), i.e for the best case there is only one peek == next, it takes log(K), and for the worst case, all objects in the heap == next, so it takes Klog(K). So this loop is not necessarily < KN. That's why the heap solution is slower than the KN solution.

It's true to take `O(nklogk)` in the worst case, when all elements have equal keys in heap (delete then insert). But I'm doubted of the test cases. Ok, leave my TLE minimum heap code as a note

``````class PriorityQueue
attr_accessor :array, :n, :comparison

def initialize(arr = [], &comparison)
@n = arr.length

@array = arr
@array.unshift nil

@comparison = comparison || ->(a,b){ a < b }

build
end

def insert(node)
self.n += 1
array[n] = node
swim(array, n, n)
end

def delete_min
return nil if n < 1

min = array[1]

swap(array, 1, n)
self.n -= 1
sink(array, 1, n)

return min
end

def get_min
return nil if n < 1

array[1]
end

def size
n
end

private

def build
(n/2).downto(1) do |k|
sink(array, k, n)
end
end

def swap(array, i, j)
t = array[i]; array[i] = array[j]; array[j] = t
end

def sink(array, k, n)
while 2*k <= n
j = 2*k
j += 1 if j+1 <= n && less(j+1, j)

break if !less(j, k)

swap(array, j, k)
k = j
end
end

def swim(array, k, n)
while k/2 >= 1
j = k/2

break if !less(k, j)

swap(array, j, k)
k = j
end
end

def less(i, j)
comparison[ array[i], array[j] ]
end
end

# Use Priority Queue O(n*logk)
def nth_super_ugly_number(n, primes)
numbers = [1]

idx = [0]*primes.count

pair = Struct.new(:key, :value)
candidates = primes.map do |prime|
key   = prime # prime*numbers[0]
value = prime
pair.new(key, value)
end
# Minimum heap
heapq = PriorityQueue.new(candidates){|a,b| a.key < b.key}

(n-1).times do
min = heapq.get_min.key
numbers << min

while min == heapq.get_min.key
min_pair = heapq.delete_min
prime    = min_pair.value

i = primes.index(prime)
idx[i] += 1

new_pair = pair.new( prime * numbers[ idx[i] ], prime )
heapq.insert(new_pair)
end

end

numbers[n-1]
end

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.