Find the smallest subarray length whose sum of elements is >= k

By | November 20, 2021 Find the smallest subarray length whose sum of elements is >= k

Problem

Given an array of integers and a number k, find the smallest subarray with a sum greater than or equal to the k

Brute Force Approach

A straightforward approach is to utilize two nested loops. The outer loop selects a starting element, while the inner loop considers all items on the right side of the current element to be ending elements. If the sum of the items between the current start and finish is more than or equal to the provided number, update the result if the current length is less than the shortest length thus far.

This approach takes O(N2) time. Let’s look at another approach.

Efficient approach

This may be rephrased as a problem regarding array’s prefix sums. Allow P[i] to equal arr + arr +… + arr[i-1]. We are looking for the smallest (yx) such that y > x and P[y] – P[x] >= k.

Let f(y) be the greatest x such that P[x] = P[y] – k, motivated by that equation. Two crucial observations are required:

• If x1 < x2 and P[x2] <= P[x1], then f(y) can never be x1, as if P[x1] <= P[y] – k, then P[x2] <= P[x1] <= P[y] – K but yx2 is smaller. This implies that our candidates x for f(y) will have increasing values of P[x].
• If f(y1) = x, then we do not need to consider this x again. For if we find some y2 > y1 with f(y2) = x, then it represents an answer of y2x which is larger than y1x.

The solution can be implemented using deque. Double Ended or Deque Queue is an extended version of the Queue data structure that supports insert and delete operations at both ends.

This approach takes O(N) time and O(N) auxiliary space.

C++ Programming

#include<bits/stdc++.h>
using namespace std;
int shortestSubarray(vector<int>& arr, int k) {
int n=arr.size();
int i;
int ans=INT_MAX;
int P[n+1];  //store prefix sums
P=0;
for(i=0;i<n;i++)
P[i+1]=P[i]+arr[i];

deque<int> q;
for(i=0;i<n+1;i++)
{
while(!q.empty()&&P[i]-P[q.front()]>=k)
{
q.pop_front();

}
while(!q.empty()&&P[i]-P[q.back()]<=0)
{
q.pop_back();
}
q.push_back(i);   // push current index
}
if(ans==INT_MAX)
return -1;
return ans;

}

int main(){
vector<int>v{1, 2, 3, 4};
int k = 3;
cout<<shortestSubarray(v, k);
}

Output

1

Python Programming

import collections
def shortestSubarray(arr, k):
P = 
for element in arr:
P.append(P[-1]+element)

q = collections.deque()
ans = float(1000000)
for i,summ in enumerate(P):

while(q and q[-1] >=summ):
q.pop()

while q and summ - q >= k:
ans = min(i-q, ans)    #update the answer
q.popleft()

q.append([i,summ])    #add index into the queue
return ans if ans!= float(1000000) else -1

l = [1, 2, 3, 4]
k = 3
print(shortestSubarray(l, k))

Output

1

Java Programming

class Solution {

static int shortestSubarray(int arr[], int n, int x)
{
int sum = 0, ans = n + 1;

int start = 0, finish = 0;
while (finish < n) {

while (sum <= x && finish < n)
sum += arr[finish++];
while (sum >= x && start < n) {
if (finish - start < ans)
ans = finish - start;

sum -= arr[start++];
}
}
return ans;
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int x = 3;
int n = arr.length;
int res = shortestSubarray(arr, n, x);
if (res == n + 1)
System.out.println("Does not exists");
else
System.out.println(res);
}
}

Output

1 