{"id":2325,"date":"2020-07-29T07:34:30","date_gmt":"2020-07-29T07:34:30","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2325"},"modified":"2022-03-31T12:08:31","modified_gmt":"2022-03-31T12:08:31","slug":"sum-subarray","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/sum-subarray\/","title":{"rendered":"Sum Subarray"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Queues.<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

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. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

EXAMPLE:<\/strong><\/h4>\n
Input\n6 7\n1 2 3 4 2 1\n\nOutput\n2<\/code><\/pre>\n
Observation:<\/h3>\n
\n
We can simply solve this problem with the help of best online programming courses:
\nStoring the current sum of all the elements in the queue.
\nIterate over all the elements of the array in the following manner.
\nIf sum >=k , best size of queue = min(best size of queue,current size of queue)
\nIf sum=k, pop queue.<\/p>\n<\/blockquote>\n
EXPLANATION:<\/h3>\n
\n
Steps:<\/p>\n
Make a prefix sum array<\/p>\n
Declare an empty deque to store the index of prefix sum<\/p>\n
Loop each prefix sum in the prefix sum array<\/a>
\nwhile 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 <\/p>\n
now
\nwhile 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
\nadd the index of current prefix sum to the dequeue<\/p>\n<\/blockquote>\n
SOLUTIONS:<\/h3>\n\t\t\t\t\t\t