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 s, int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int resultLength = int.MaxValue;

            int startIndex = 0;

            int sum = 0;

            for (int i = 0; i < nums.Length; ++i)

            {

                sum += nums[i];

                while(sum >= s)

                {

                    resultLength = Math.Min(resultLength, i - startIndex + 1);

                    sum -= nums[startIndex++];

                }

            }

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

        }

Complexity: O(n)