{"id":2826,"date":"2024-03-24T14:17:46","date_gmt":"2024-03-24T14:17:46","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2826"},"modified":"2025-04-07T12:33:37","modified_gmt":"2025-04-07T12:33:37","slug":"minimum-size-subarray-sum","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/minimum-size-subarray-sum\/","title":{"rendered":"Minimum Size Subarray Sum Problem (C++, Java, Python)"},"content":{"rendered":"\n

One of the difficult topics in programming is the Sliding Window<\/a>. It helps you to solve problems in a lower time complexity. This method is useful when we are solving problems related to subarrays or substrings. In this article, we will discuss the problem \u201cMinimum Size Subarray Sum,\u201d which is based on a sliding window.<\/p>\n\n\n\n

\u201cMinimum Size Subarray Sum\u201d Problem<\/strong><\/h2>\n\n\n\n

In the Minimum Size Subarray problem, you are given an array of integers. You have also been given a target integer. You have to find the minimum length subarray such that the sum of elements present in the subarray is equal to or greater than the target element. <\/strong><\/p>\n\n\n\n

Let\u2019s understand this with an example:<\/p>\n\n\n\n

Input:<\/strong> <\/p>\n\n\n\n

array = [ 2, 3, 1, 4, 2, 1], target = 6.<\/code><\/pre>\n\n\n\n
Output:<\/strong> <\/p>\n\n\n\n
2<\/code><\/pre>\n\n\n\n
Explanation:<\/strong> Shown are different ways in which we can form 6 and the minimum length among them is 2. So the answer is 2.<\/p>\n\n\n\n
Brute Force Approach<\/strong><\/h2>\n\n\n\n
The basic approach is to create all the subarrays of the given array. Check whose subarray sum is greater than the target element. If it is greater than the target element,t find the minimum length among them. Let\u2019s understand this step by step.<\/p>\n\n\n\n
    \n
  1. Create a loop that traverses from 1 to n. Where n is the size of the array.<\/li>\n\n\n\n
  2. Create a variable \u2018sum\u2019 that stores the total subarray sum.<\/li>\n\n\n\n
  3. Create a nested loop that traverses from i to n. Now we get the subarray of size (j – i +1<\/strong>).<\/li>\n\n\n\n
  4. Check if the subarray sum is greater than the target element or not. If it is, then compare its size with our resultant variable.<\/li>\n\n\n\n
  5. If a resultant variable is greater than the size of the subarray. Update the resultant with this size.<\/li>\n\n\n\n
  6. After iterating over all the subarrays. Return the resultant variable.<\/li>\n<\/ol>\n\n\n\n
    The time complexity for the above code is O(n^2)<\/strong>. Where n is the size of the array. We are using two nested loops whose time complexity is O(n^2). The space complexity for the above code is O(1) as we are not using any extra space.<\/p>\n\n\n\n
    Binary Search Approach<\/strong><\/h2>\n\n\n\n
    In the above approach, we see we are using O(n^2) time complexity, which is huge. In this approach, we will calculate the subarray sum for index 1 and store it in a vector. Now we will go at each index and check for their lower bound using binary search<\/a>. If the size of the lower bound is less than the resultant variable,e, we will update it.\u00a0<\/p>\n\n\n\n
    Let\u2019s examine this approach step by step.<\/p>\n\n\n\n