Table of Contents

Leetcode 209. Minimum Size Subarray Sum

##### Problem

Given an array of positive integers `nums`

and a positive integer `target`

, return the minimal length of a **contiguous subarray** `[nums`

of which the sum is greater than or equal to _{l}, nums_{l+1}, ..., nums_{r-1}, nums_{r}]`target`

. If there is no such subarray, return `0`

instead.

**Example 1:**

Input:target = 7, nums = [2,3,1,2,4,3]Output:2Explanation:The subarray [4,3] has the minimal length under the problem constraint.

**Example 2:**

Input:target = 4, nums = [1,4,4]Output:1

**Example 3:**

Input:target = 11, nums = [1,1,1,1,1,1,1,1]Output:0

**Constraints:**

`1 <= target <= 10`

^{9}`1 <= nums.length <= 10`

^{5}`1 <= nums[i] <= 10`

^{5}

**Follow up:** If you have figured out the `O(n)`

solution, try coding another solution of which the time complexity is `O(n log(n))`

.

Source : Leetcode 209. Minimum Size Subarray Sum

##### Solution Approach – 1: Two Pointers

We can use two pointer approach to solve this problem. Please do not get confused with pointers of C or C++ or any other languages. Here, **by pointer we simply mean index of the array**.

Two pointer (or index) **i** and **j** will initially point to the first index of the given array. Then **j** will move forward and we will keep track of the summation of elements **j** passes. When summation will be **>= target**, we will move **i** forward **until summation becomes < target**. During this process of i’s movement, we will keep track of the length between **i** and **j** and save the minimum length.

###### C++ Code

class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int len = nums.size(); if(len == 0) return 0; int i = 0; int j = 0; int sum_so_far = 0; int min_subarray_length = INT_MAX; // variable j will move forward and update sum_so_far // variable i will wait at his position while(j < len){ sum_so_far += nums[j]; /* when sum_so_far is >= target, that length is a possible answer. We will update our answer with that. But, may be, if we eleminate zero or more element from the position of i, sum_so_far might not be reduced that much to become < target. So, we will try to eliminate elements from the position of i and check if sum_so_far is still >= target or not. */ while(sum_so_far >= target && i <= j){ min_subarray_length = min(min_subarray_length, j - i + 1); sum_so_far -= nums[i]; //eliminate the i-th element i++; // and move i forward towards j } j++; } if(i == 0) // that measn, we never found sum_so_far to be >= target return 0; //hence, there is no contiguous subarray and min_subarray_length = 0 return min_subarray_length; } };

##### Conclusion

This is a medium level leetcode problem that can be solved using both two pointer and binary search approach. If you like the way we explained it, please write a comment. If you hate it, write comment as well. 🙂 There are other posts you may like listed below.

Happy Coding! 🙂