Grokking the Coding Interview: Patterns for Coding Questions

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

.....

.....

.....

Like the course? Get enrolled and start learning!
M

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)