Shortest Subarray with Sum is at least k | Algorithms Notes

Shortest Subarray with Sum is at least k | Algorithms Notes

Given an integer array A of length n and a number k, design a linear time algorithm to find the shortest subarray whose sum is at least k.

Solution:

Let P[i] be the sum of A[1..i]. For an ending index e, we want to compute the largest index b, such that the sum of A[b..e] = P[e+1] – P[b] is at least k. If there exists i and j, such that i < j and P[i] > P[j], then i cannot be the answer for any ending index at least j. Hence, we can maintain a queue q initialized empty. The queue stores indices increasing by position and also by P value. When processing A[i], dequeue all elements x, such that P[i+1] – P[x] is at least k. The last dequeued element is the optimal solution ending at i and we can update the current optimal solution. Then, enqueue i if P[i] is larger than the P value of the tail of the queue. Since every index will be considered as a starting index and an ending index only once, this algorithm runs in linear time.

解法：

令P[i]為A[1..i]的總和。對於一結尾索引e而言，我們想要計算最大的索引b使得A[b..e] = P[e+1] – P[b]至少為k。如果存在i及j，使得i < j且P[i] > P[j]，那麼i不可能是至少為j的結尾的最佳解。 因此，我們維護一個佇列q初始為空。此佇列儲存的陣列的索引值，且依照索引以及P值的大小遞增。當處理到A[i]時，把所有x使得P[i+1] – P[x] ≥ k從佇列中移除。最後一個移除的元素即是在i結尾的最佳解。所以我們可以依此更新當前最佳解。接著，如果P[i]大於佇列尾端索引的P值，那麼就把i enque。因為每個索引只會被考慮為開始和結束各一次，此演算法時間為線性。

Read full article from Shortest Subarray with Sum is at least k | Algorithms Notes