Sliding Window

When to Use It

The problem involves a linear data structure (array, list, string) and asks to find a contiguous sub-section (subarray or substring) that is optimal in some way (longest, shortest, max sum, etc.).

Keywords & Signals

contiguous subarray
substring
longest/shortest length
max/min sum
contains k distinct elements

Typical Problem

Given an array of integers, find the maximum sum of any contiguous subarray of size k.

Big O Notation
The performance characteristics of this algorithm.

Time Complexity

Best

O(n)

Average

O(n)

Worst

O(n)

Space Complexity

Worst

O(1) or O(k)

Code Templates
Basic templates in Python and JavaScript to get you started.
function slidingWindow(arr, k) {
  // Implementation details
  let maxSum = 0;
  let windowSum = arr.slice(0, k)
    .reduce((a, b) => a + b, 0);
  maxSum = windowSum;

  for (let i = 0; i < arr.length - k; i++) {
    windowSum = windowSum - arr[i] + 
                arr[i + k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}