Last Updated on March 31, 2022 by Ria Pathak
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
2Observation:
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 uselessnow
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.