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
using namespace std;
int32_t main()
{
    int n,k;
    cin>>n>>k;
    int A[n];
    for(int i=0;i>A[i];
    }
    int sum=0;
    int i=0;
    queueq;
    int ans=INT_MAX;
    while(i=k)
        {
            while(sum>=k)
            {
                if(sum>=k)
                {
                    int temp=q.size();
                    ans=min(ans,temp);
                }
                sum-=q.front();
                q.pop();
            }
        }
        i++;
    }
    cout<




						 
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 monoq = new LinkedList(); //opt(y) candidates, as indices of P
         int len=P.length; 
        for (int y = 0; 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
						 
from queue import PriorityQueue
n = int(input())
p = list(map(int,input().split()))
m = list(map(int,input().split()))
c = list(map(int,input().split()))
pq = PriorityQueue()
qu = []

for i in range(n):
	pq.put(p[i] + m[i] + c[i])

Q = int(input())

for i in range(Q):
	q = int(input())
	
	if q > pq.qsize():
		print(-1)
	else:
		
		for j in range(1, q):
			top = pq.get()
			pq.put(top)
			qu.push(top)
			pq.get()
		
		top = pq.get()
		pq.put(top)
		print(top, end = " ")
		pq.get()

		while qu:
			pq.put(qu[0])
			qu.pop(0)

[forminator_quiz id="2327"]

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

This article tried to discuss Queues. Hope this blog helps you understand and solve the problem. To practice more problems on Queues you can check out MYCODE | Competitive Programming.

Leave a Reply

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