Minimum Size Subarray Sum

Problem: Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 12, nums = [2,3,1,5,8,3]
Output: 2
Explanation: the subarray [5,8] has the minimal length under the problem constraint.

Approach: Keep 2 pointers, one for the start and another for the end of the current subarray and make optimal moves so as to keep the sum greater than s as well as maintain the lowest size possible. Here are the steps which we can follow:

• Initialize startIndex to 0, currSum to 0 and result to INT_MAX.
• Foreach i where i = 0 to n:
• Add array[i] to currSum 
• WHILE currSum >= s
• result = MIN (result, i - startIndex + 1); // min of result and length of current sub array
• At this point we can safely increment the startIndex as min subarray starting with this index where currSum >= s is found already.
• currSum -= array[startIndex]
• startIndex += 1

Now we can return result if it is not INT_MAX otherwise 0.

Implementation in C#:

    public int MinSubArrayLen(int target, int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int minLength = int.MaxValue;

        int start = 0;

        int currSum = 0;

        for (int end = 0; end < length; ++end)

        {

            currSum += nums[end];

            while (currSum >= target)

            {

                minLength = Math.Min(minLength, end - start + 1);

                currSum -= nums[start++];

            }

        }

        return minLength == int.MaxValue ? 0 : minLength;

    }

Complexity: O(n)