Sliding Window — Efficient Subarray Processing
sliding-windowarraysalgorithmsintermediatefree
The sliding window pattern — process contiguous subarrays and substrings in O(n) by expanding and contracting a window.
What Is the Sliding Window?
The sliding window technique maintains a "window" — a contiguous subset of an array or string — and slides it across the data. Instead of recalculating everything for each possible window position, you update incrementally as the window moves.
Fixed-size windows slide one step at a time. Variable-size windows expand and contract based on conditions.
python
def max_sum_subarray(arr, k):
if len(arr) < k:
return None
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
print(f"Array: {arr}")
print(f"Window size: {k}")
print(f"Max sum: {max_sum}")
return max_sum
max_sum_subarray([2, 1, 5, 1, 3, 2], 3)
print()
max_sum_subarray([4, 2, 1, 7, 8, 1, 2, 8, 1, 0], 3)python
def min_subarray_len(target, arr):
left = 0
current_sum = 0
min_len = float("inf")
for right in range(len(arr)):
current_sum += arr[right]
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= arr[left]
left += 1
result = min_len if min_len != float("inf") else 0
print(f"Target: {target}, Array: {arr}")
print(f"Minimum subarray length: {result}")
return result
min_subarray_len(7, [2, 3, 1, 2, 4, 3])
print()
min_subarray_len(11, [1, 1, 1, 1, 1, 1, 1, 1])Key Takeaways
- Fixed window: slide a window of size k, update by adding the new element and removing the old. O(n).
- Variable window: expand right to include, contract left to optimise. O(n) with two pointers.
- The sliding window pattern applies to subarray sums, longest/shortest substrings, and max/min within a range.
- It turns O(n²) or O(n×k) brute force into O(n) by reusing computation from the previous window position.