Minimum Size Subarray Sum

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 [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: 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 <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

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! 🙂