Problem
Shortest Subarray with Sum at Least K
Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.
If there is no non-empty subarray with sum at least K, return -1.
Example 1:
Input: A = [2,-1,2], K = 3
Output: 3
Input: A= [2,-1,1,2,-1,2,2,-1,-2], K = 5
Output: 4
Input: A = [1,2], K = 4
Output: -1
Example 3
Input: A= [2,-1,1,2,-1,2,2,-1,-2], K = 5
Output: 4
Note:
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
Solution
The brutal force way is, for 0 to N, for each index, search on the right for the first subarray sum at least K. After go through all the indexes, we return the shortest Subarray that with sum at least K. The cost is O(N^2).
A slightly better brutal force solution is to try 1 element combinations, then 2 element combinations, then 3 element combinations, until we found solution then exit, or go through all the possible scenarios, then return -1. The cost is still O(N^2), but may exit earlier than the other brutal force with luck.
A better solution can find the answer in O(N) if we step back and think about what we are doing.
This problem is equivalent to an investment problem on stock market. The array is the every day gain and loss. The problem is to find the buy day and sell day for a stock, in order to achieve gain higher than K. The gain between day i and day j is the sum(j) - sum(i). Our goal is to achieve the target gain in the shortest time possible.
This problem is equivalent to an investment problem on stock market. The array is the every day gain and loss. The problem is to find the buy day and sell day for a stock, in order to achieve gain higher than K. The gain between day i and day j is the sum(j) - sum(i). Our goal is to achieve the target gain in the shortest time possible.
 |
| stock price |
With some common sense, we know the stock price has up and downs. In order to achieve the gain in shortest time possible, we will never trade at the down slope. For buying stock, if we buy at down slope, we start to loose money right away. We would rather wait for the down slope is over, then we buy. In that case, we enter later but achieve the target gain earlier. Simply because if we enter later, our net gain that day is 0 instead of negative! The sell can only happen at uphill as well. If we could sell at a downhill and still have gain larger than K, why not sell it earlier, when the price is higher? Another observation is, we buy at day A, as soon as the gain K is reached at day B, we want to sell immediately. Waiting longer won't help our goal, there is no shorter period of get back our investment than right now. With these observations, we can code as if we are trading the stock.
One more detail, the first day is uphill or down hill is decided by comparing to 0. Positive is uphill, negative is downhill. That is the reason we have sum array with size N+1 instead of N.
import java.util.*;
public class InvestmentCycle {
public static int shortest(int[] a, int gain) {//2,-1,2
int N = a.length;
Deque<Integer> deque = new LinkedList<>();
int[] sum = new int[a.length+1];
int min = N+1;
for(int i = 0; i < a.length; i++) {
sum[i+1] = sum[i] + a[i];//{0, 2, 1, 3}
}
for(int i = 0; i < sum.length; i++) {
if(i > 0 && sum[i] <= sum[i-1]) {continue;} //don't sell at downhill
while(!deque.isEmpty() && sum[i] <= sum[deque.getLast()]) { //don't buy at downhill
deque.removeLast();
}
while(!deque.isEmpty() && sum[i] - sum[deque.getFirst()] >= gain) {
min = Math.min(min, i - deque.removeFirst());//no better opportunity later with this start date
}
deque.addLast(i);//next start date to consider
}
return (min == N+1)?-1:min;
}
public static void main(String...args) {
System.out.println(shortest(new int[]{2,-1,2}, 3));
System.out.println(shortest(new int[]{1,2}, 4));
System.out.println(shortest(new int[]{2,-1,1,2,-1,2,2,-1-2}, 5));
System.out.println(shortest(new int[]{1}, 1));
}
}
public class InvestmentCycle {
public static int shortest(int[] a, int gain) {//2,-1,2
int N = a.length;
Deque<Integer> deque = new LinkedList<>();
int[] sum = new int[a.length+1];
int min = N+1;
for(int i = 0; i < a.length; i++) {
sum[i+1] = sum[i] + a[i];//{0, 2, 1, 3}
}
for(int i = 0; i < sum.length; i++) {
if(i > 0 && sum[i] <= sum[i-1]) {continue;} //don't sell at downhill
while(!deque.isEmpty() && sum[i] <= sum[deque.getLast()]) { //don't buy at downhill
deque.removeLast();
}
while(!deque.isEmpty() && sum[i] - sum[deque.getFirst()] >= gain) {
min = Math.min(min, i - deque.removeFirst());//no better opportunity later with this start date
}
deque.addLast(i);//next start date to consider
}
return (min == N+1)?-1:min;
}
public static void main(String...args) {
System.out.println(shortest(new int[]{2,-1,2}, 3));
System.out.println(shortest(new int[]{1,2}, 4));
System.out.println(shortest(new int[]{2,-1,1,2,-1,2,2,-1-2}, 5));
System.out.println(shortest(new int[]{1}, 1));
}
}
The time cost is O(N) and the space cost is O(N) as well.
