Minimum Size Subarray Sum greater or equal K

Problem:

Given an array of positive integers nums and a positive integer target, return the

minimal length of a contiguous subarray of which the sum is greater than or equal(>=) to target. If there is no such subarray, return 0 instead.

Example, nums = [2,3,1,2,4,3] and target = 7, the minimum subarray length should be 2, that is [4,3]

Approach:

We can solve this problem using two methods. The first one is the Prefix sum + Binary search approach and another one is the Two pointer approach.

Let's discuss the first one,

We all know how Prefix sum works, in every ith position it will store the previous all elements sum including current(ith) position, right?

So, now let's illustrate it.

After building the prefix sum array we have to make some observations.

~How can we get our target value !
~How can we choose minimal length subarray
Suppose we're at a position 'i' and we need 'X' number, we can get it if and only if there is another value 'Y', that is,
Current[i] - X = Y
It's really easy to understand,
     prefix[i] - prefix[j] = target

=>prefix[i] - target = prefix[j]
Hence the prefix array is sorted, for finding the prefix[j] we can do a binary search( upper bound can do this). If we get the position of prefix[j] we can simply update our answer by (i-j+1)

Time Complexity : O(n*log(n)), log(n) for binary search

Simple Code: