0% completed
Solution: Sum of Elements
Problem Statement
Given an array, find the sum of all numbers between the K1’th and K2’th smallest elements of that array.
Example 1:
Input: [1, 3, 12, 5, 15, 11], and K1=3, K2=6
Output: 23
Explanation: The 3rd smallest number is 5 and 6th smallest number 15. The sum of numbers coming
between 5 and 15 is 23 (11+12).
Example 2:
Input: [3, 5, 8, 7], and K1=1, K2=4
Output: 12
Explanation: The sum of the numbers between the 1st smallest number (3) and the 4th smallest
number (8) is 12 (5+7).
Solution
This problem follows the `Top ‘K’ Numbers pattern
.....
.....
.....
Chingyuan Wang
· 4 years ago
Why isn't heapify used? It's faster at o(n) instead of o(nlogn) with n heappushes.
Ryan Chibana
· 4 years ago
Why would we ever push everything onto a heap? Sorting and summing the subarray would be faster.
Shan
· 4 years ago
Correct complexity analysis:
Time: nlogn
Gary
· 4 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
Michael Shum
· 3 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)
lejafilip
· 2 years ago
Quickselect works and give us O(n) in average
Spencer Lan
· 8 months ago
max heap is native now in the latest version of Python. Will the IDE be updated to utilize this?