209.minimum-size-subarray-sum.md

209. Minimum Size Subarray Sum

Clarification Questions

• Is the input array sorted?

Test Cases

Normal Cases

Input: nums = [2,1,4,1,3], target = 8
Output: 3

Input: nums = [1,3,4], target = 4
Output: 1

Input: nums = [1,3,2,1,1], target = 4
Output: 2

Input: nums = [1,1,1], target = 5
Output: 0

Edge / Corner Cases

TODO: Can't think of any edge cases.

Prefix Sum (Not Optimal)

We can apply prefix sum approach to find the sum of subarray.

nums =   1, 2, 3, 1, 2
prefix = 1, 3, 6, 7, 9
            i  
                  j
               |--|

Then prefixSum(j) - prefixSum(i) = sum of subarray(i + 1..j)

fun minSubArrayLen(target: Int, nums: IntArray): Int {
    var result = Int.MAX_VALUE
    val prefixSum = IntArray(nums.size)
    prefixSum[0] = nums[0]
    for (i in 1 until nums.size) {
        prefixSum[i] = prefixSum[i - 1] + nums[i]
    }
    for (i in 0 until nums.size) {
        for (j in i until nums.size) {
            // prefixSum[j] = prefixSum[i] = sum of subarray(i + 1..j)
            // adding nums[i] to get sum of subarray(i..j)
            var sum = prefixSum[j] - prefixSum[i] + nums[i]
            if (sum >= target) {
                result = minOf(result, j - i + 1)
            }
        }
    }
    return if (result == Int.MAX_VALUE) 0 else result
}

• Time Complexity: O(n^2).
• Space Complexity: O(n) for prefix sum array.

Sliding Window

• Window: the subarray that its sum >= target.
• We keep starting index fixed and keep expanding the ending index until the sum of [start..end] >= target.
• Then we reduce the window size by increasing the starting index until [start..end] < target so that we can get the minimum size of subarray that meets the requirement.

fun minSubArrayLen(target: Int, nums: IntArray): Int {
    var sum = 0
    var left = 0
    var ans = Int.MAX_VALUE
    for (right in nums.indices) {
        sum += nums[right]
        // The window is valid, then try to minimize it
        while (sum >= target) {
            // We update the result here, because the window is valid
            ans = minOf(ans, right - left + 1)
            sum -= nums[left]
            left++
        }
    }
    // It's possible that all sum < target, so we return 0
    return if (ans == Int.MAX_VALUE) 0 else ans
}

// Or equivalently, followed our general sliding window template.
fun minSubArrayLen(target: Int, nums: IntArray): Int {
    var minLength = Int.MAX_VALUE
    var start = 0
    var end = 0
    var currentSum = 0
    while (end < nums.size) {
        currentSum += nums[end]
        // We try to find the minimum size subarray sum, so we have to 
        // shrink the window to become valid and minimum size!!
        while (currentSum - nums[start] >= target) {
            currentSum -= nums[start]
            start++
        }

        if (currentSum >= target) {
            val currentLength = end - start + 1
            minLength = if (currentLength < minLength) currentLength else minLength
        }
        end++
    }
    return if (minLength == Int.MAX_VALUE) 0 else minLength
}

• Time Complexity: O(n), we move ending index and then starting index, that just scaned through array.
• Space Complexity: O(1) for no extra space.

TODO: Add binary search and two pointer solution. https://leetcode.com/problems/minimum-size-subarray-sum/solutions/59090/c-o-n-and-o-nlogn/