Google | Phone Screen | Smallest subarrays with sum equals K
I did it my way-Bloody Wing
2458
GooglePhone ScreeningInterview

Given an array arr of positive integers only and an integer k. Find the minimum length sum of the two shortest subarrays whose sum equals k.

Example 1:

Input: arr = [5, 1, 2, 2, 3, 4, 1], k = 5
Output: 3
Explanation:
Subarrays whose sum equal 'k' are [5], [1, 2, 2], [2, 3], [4, 1].
The two shortest subarrays are [5], [2, 3]. Hence len([5]) + len([2, 3]) = 1 + 2 = 3.
[5], [4, 1] also works but that does not change the final answer.
My Python solution

thoughts: Use Hastable whose key represents prefix sum and value represents corresponding index and maintain a max heap of size 2 that stores the lengths of the two shortest subarrays whose sum are both K.

# time: O(n * log(2)), space: O(n)
import queue
def min_intervals_length_sum(nums, K):
    n = len(nums)
    d = dict() # key: prefix sum; value: index
    d[0] = -1
    cur_sum = 0
    pq = queue.PriorityQueue()
    for i, num in enumerate(nums):
        cur_sum += num
        if cur_sum - K in d:
            pq.put(-(i - d[cur_sum - K]))
        if pq.qsize() > 2:
            pq.get()
        d[cur_sum] = i
    if pq.qsize() < 2:
        return -1
    else:
        total = 0
        while pq.qsize() > 0:
            total += abs(pq.get())
        return total

A=[5,1,2,2,3,4,1]
K=5
print(min_intervals_length_sum(A, K))

Follow-up:
What if the array has negative numbers?

Related problems:

Comments (7)