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

Posted in

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

Vinay Khatri
Last updated on June 9, 2022

    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[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:

    Leave a Comment on this Post

    0 Comments