Sum Subarray

Concepts Used

Queues.

Difficulty Level

Hard.

Problem Statement :

You are given an array A of size N. You have to print the length of the smallest subarray that has sum at least equal to K.

See original problem statement here

EXAMPLE:

Input
6 7
1 2 3 4 2 1

Output
2

Observation:

We can simply solve this problem with the help of best online programming courses:
Storing the current sum of all the elements in the queue.
Iterate over all the elements of the array in the following manner.
If sum >=k , best size of queue = min(best size of queue,current size of queue)
If sum=k, pop queue.

EXPLANATION:

Steps:

Make a prefix sum array

Declare an empty deque to store the index of prefix sum

Loop each prefix sum in the prefix sum array
while the current prefix sum can form a valid subarray sum with the prefix sum of the index at the head of the deque, update the result min. and poll the head out as it is useless

now
while the current prefix sum is smaller or equal to the prefix sum at the end of the deque, poll out the last of the deque
add the index of current prefix sum to the dequeue

SOLUTIONS:

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
    int n,k;
    cin>>n>>k;
    int A[n];
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
    }
    int sum=0;
    int i=0;
    queue<int>q;
    int ans=INT_MAX;
    while(i<n)
    {
        q.push(A[i]);
        sum+=A[i];
        if(sum>=k)
        {
            while(sum>=k)
            {
                if(sum>=k)
                {
                    int temp=q.size();
                    ans=min(ans,temp);
                }
                sum-=q.front();
                q.pop();
            }
        }
        i++;
    }
    cout<<ans<<endl;
}
import java.util.*;
  import java.io.*;
  public class Main {
   static int shortestSubarray(int[] A, int K) {
        int N = A.length;
        long[] P = new long[N+1];
        for (int i = 0; i < N; ++i)
            P[i+1] = P[i] + (long) A[i];

        // Want smallest y-x with P[y] - P[x] >= K
        int ans = N+1; // N+1 is impossible

        Deque<Integer> monoq = new LinkedList<Integer>(); //opt(y) candidates, as indices of P
         int len=P.length; 
        for (int y = 0; y <len ; ++y) {
            // Want opt(y) = largest x with P[x] <= P[y] - K;
            while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
                monoq.removeLast();
            while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
                ans = Math.min(ans, y - monoq.removeFirst());

            monoq.addLast(y);
        }

        return ans < N+1 ? ans : -1;
    }
    public static void main(String args[]) throws IOException {
      Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] A=new int[n];
        for(int i=0;i<n;i++)
          A[i]=sc.nextInt();
      int ans=shortestSubarray(A,k);
      System.out.print(ans);
    }
  }

Space: O(n), in worst case, the deque has to store all prefix sum in it

Previous post Quiz Test
Next post Valuable Time

Leave a Reply

Your email address will not be published. Required fields are marked *