CodeArtist
BAN USERHere is my proposal. I've divided the code into three steps for readability. This can be achieved in one iteration as well.
Time and space complexity O(n).
int minSubArrLen(vector<int>& arr, int k){
int n = arr.size();
unsigned int res = -1 //max unsigned int;
vector<int> subSum(n);
vector<int> subLen(n);
subSum[0] = arr[0];
subLen[0] = 1;
int y=0;
//Kadane's algorithm to produce all max sum sub-arrays anding at each index.
for(int i=1; i<n; ++i){
if(arr[i] >= k) //Will work also w/o it. Just an optimization.
return 1;
if(subSum[i-1] > 0){
subSum[i] = subSum[i-1] + arr[i];
subLen[i] = subLen[i-1] + 1;
}
else{
subSum[i] = arr[i];
subLen[i] = 1;
}
}
//For every sub-array which sum is more than k, try to trim it from the front:
for(int i=0; i<n; ++i){
if(subSum[i] > k){
if(y <= i - subLen[i]){
while(subSum[i]-subSum[y]>k)
y++;
}
else{
y=i;
while(y>=0 && subSum[i]-subSub[y]<k){
y--;
}
}
subLen[i] = i - y;
}
}
//Choose the minimum length sub array
unsigned minLength =-1;
for(int i=0; i<n; ++i){
if(subSum[i]>=k && subLen[i] < minLength)
minLength = subLen[i];
}
return minLength;
}
How would you produce the sub-arrays before inserting the to hash-map?
- CodeArtist December 28, 2017@charan
k may be negative.
You code will fail already for a={-1}, k=-2.
@DeathEater
- CodeArtist January 31, 2018Check this case:
arr = {-2,2,-2,1,1,1,1} k=2.