Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Sum of Elements (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Quickselect works and give us O(n) in average

A

Anonymous

· 4 years ago

Instead of pushing all elems to heap, we can enforce the minHeap has a size of K2. Then, pop K1 elems off the heap. Pop + Sum the rest of the elems on the Heap.

That should give us have a runtime of O(N*logK2)

A

Anonymous

· 4 years ago

Why would we ever push everything onto a heap? Sorting and summing the subarray would be faster.

Show 1 reply
A

Anonymous

· 4 years ago

Why isn't heapify used? It's faster at o(n) instead of o(nlogn) with n heappushes.

A

Anonymous

· 4 years ago

Correct complexity analysis:

Time: nlogn

A

Anonymous

· 5 years ago

The max heap solution gives 23 for following inputs:

input = [3, 5, 8, 7], k1=2, k2=7

when the answer should be 15 because it's popping off all elements from max_heap in the last for loop.

I needed to change it to as follows to get the correct answer:

upper_bound = min (k2 - k1 - 1, input_size - k1)

for i in range (upper_bound): if max_heap: sum += -heapq.heappop(max_heap) else: break

If i use k2=9 instead, I get index out of range error from official max heap solution because it tries to pop too many times

Show 1 reply

Reading Progress

0%

Vote for new content