[Array + Two Pointers] LC 209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

Goal

  • Given an array of positive integers
  • minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target
  • *Greedy or Sorting is not allowed!

Strategy

  • Iterate through the array and add each element to the sum, one at the time
  • During each iteration, we can keep subtracting the numbers (from sum) from the left until it < target

Highlight

  • classic two pointers
  • concept of sliding & shrinking the left window (usually a while loop)

Complexity

  • Time: O(N) → as we iterate the array once
  • Space: O(1) → didn’t occupy any extra space by creating additional data structures

Code

Data Engineering & Analytics