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

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 the array's prefix sums. Allow P[i] to equal arr[0] + arr[1] +... + arr[i-1]. We are looking for the smallest ( y - x ) 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 x 1 < x 2 and P [x2] <= P [x1], then f ( y ) can never be x 1, as if P [x1] <= P [y] - k , then P [x2] <= P [x1] <= P [y] - K but y - x2 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 y2 - x, which is larger than y1 - x .

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]=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)
        {
            ans=min(ans,i-q.front());   // update the answer
            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 = [0]
        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][1] >=summ):
                q.pop()
            
            while q and summ - q[0][1] >= k:
                ans = min(i-q[0][0], 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

People are also reading:

• Merge Two Sorted Arrays in-place
• Find whether an array is subset of another array
• Find the maximum product of two integers in an array
• Rearrange an array such that arr[i] = i
• WAP to Count no. of alphabets, digits and spaces present in a file
• WAP to Print Square Using * Character
• Print a given matrix in spiral form
• Write a Program to read from a text file and then write in another text file
• WAP to display a message on screen
• WAP to calculate the Factorial of an Integer