Longest subarray whose sum <= k
by e2718281828459045
Longest subarray whose sum
Given an array of numbers and a key , find the longest subarray of for which the subarray sum is less than or equal to .
This problem is from the book “Elements of Programming Interviews”.
This problem has a rather easy quadratic time complexity algorithm: check each pair of indices , where to see if the sum of the subarray is no greater than , and return the pair with the largest difference . To avoid repeatedly computing the subarray sum, one can first preprocess the array to get an array of partial sums, where , for , and by definition, . Then the subarray sum can be obtained as . The preprocessing takes linear time and linear space.
In the following we describe an algorithm with time complexity .
Algorithm LONGESTSUBARRAY(, )
Input: An array and a real number
Output: A pair of indices , maximizing , subject to
1. Compute the array of partial sums, where is the prefix sum of the first numbers in . .
2.
3.
4.
5. for down to 0
if
6.
7. for up to
if
Use binary search to look for the rightmost element in such that . If such an element exists, update to if
8. return
Correctness of the Algorithm
The key is to observe the following two facts.
Claim: (1) If two indices satisfies that , then cannot appear in an optimum solution; (2) If two indices satisfies that , then cannot appear in an optimum solution.
Proof: For any index , , note that the subarray sum of is less than the subarray sum of , and the length of the subarray $A[i..r’]$ is greater than the length of the subarray (although both length might be negative, but the statement still holds). Therefore, is preferable over . This is also the reason why we compute the strictly increasing sequence of .
The second statement follows a similar reasoning.
Time Complexity and Space Complexity
Step 1, computing the prefix sums, takes time. Step 4, computing the array , takes time. Step 7 takes time as each iteration takes time.