Subarray Sum
1 min read

Subarray Sum

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

Solution

   fun minSubArrayLen(target: Int, nums: IntArray): Int {
        var minLen = Int.MAX_VALUE
        var windowStart = 0
        var windowSum = 0

        for (windowEnd in nums.indices) {
            windowSum += nums[windowEnd]
            while (windowSum >= target) {
                minLen = kotlin.math.min(minLen, windowEnd + 1 - windowStart)
                windowSum -= nums[windowStart++]
            }
        }

        return minLen.takeIf { minLen != Int.MAX_VALUE } ?: 0
    }
  1. First, we will add-up elements from the beginning of the array until their sum becomes greater than or equal to target.
  2. These elements will constitute our sliding window. We are asked to find the smallest such window having a sum greater than or equal to target. We will remember the length of this window as the smallest window so far.
  3. After this, we will keep adding one element in the sliding window (i.e. slide the window ahead) in a stepwise fashion.
  4. In each step, we will also try to shrink the window from the beginning. We will shrink the window until the window’s sum is smaller than target again. This is needed as we intend to find the smallest window. This shrinking will also happen in multiple steps; in each step, we will do two things:
  • Check if the current window length is the smallest so far, and if so, remember its length.
  • Subtract the first element of the window from the running sum to shrink the sliding window.