Problem Solving - Sliding Window

Recap & Goals

Recap

What patterns have we seen so far?

Frequency counters
Multiple pointers

Goals

Describe the sliding window technique
Discuss how to identify a sliding window problem
Explain how sliding window reduces time complexity

Sliding Window

What is Sliding Window?

A possible technique when the input is an iterable type
like an array or string
A sliding window is generally a subset of the elements in the array
or characters in the string
Dynamically expand and shrink the window depending on some condition
Closely related to multiple pointers because it often involves pointers (start and end of the window)

Sliding Window Visualized

Given a list [a b c d e f g h], let’s slide a window of 3 elements wide:

[a b c d e f g h]

Here goes the window through the loop:

[a b c] -> first iteration
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h] -> last iteration

How Does Sliding Window Work?

Sliding window works by making use of something called an
optimal substructure.

The TL;DR is that if you break a problem into sub-problems and solve those, you’ll get the solution to the original problem.

In our case, one of the possible “windows” is the solution to the problem.

When Does Sliding Window Work?

Sliding window works by reducing an O(n^2) approach to O(n).

Examples include:

min/max of some sequence
longest/shortest sequence of some iterable
generate permutations or subsequences

In general, look for the keywords subarray or substring, and see if the naive solution is O(n^2). This may be an indication to use sliding window.

Sliding Window Example

Example: Max Sum of a Contiguous Subarray

Write a function called maxSubarraySum, which accepts an array of integers and a number representing the length of a subarray.

The function should return the largest sum of a contiguous subarray
with the given length.

Note that a subarray must consist of
consecutive elements from the original array.

Example: Max Sum of a Contiguous Subarray

maxSubarraySum([100, 200, 300, 400], 2); // 700

maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4); // 39

maxSubarraySum([-3, 4, 0, -2, 6, -1], 2); // 5

maxSubarraySum([3, -2, 7, -4, 1, -1, 4, -2, 1], 2); // 5

maxSubarraySum([2, 3], 3); // null

In the example above, [100, 200] is a valid subarray of the original array, but [100, 300] is not, because 100 and 300 are not consecutive.

Naïve (Brute Force) Solution

Compute the sum for every possible sub-array with size k at every index.

demo/mSSBrute.js

function maxSubarraySum(arr, k) {
  let maxSum = 0;

  for (let i = 0; i <= arr.length - k; i++) {
    // sum every k elements starting from current i
    let currentSum = 0;
    for (let j = i; j < i + k; j++) {
      currentSum += arr[j];
    }
    // is this the largest slice so far?
    maxSum = Math.max(currentSum, maxSum);
  }

  return maxSum;
}

Time Complexity: O(n^2)

Naïve Solution Visualized

For ([-3, 2, 3, -1, 5, 1], 3) as input,

How many times did we add three to a currentSum?

How many times did we do 3 + -1?

Naïve Solution Critique

We’re doing the same work over and over, re-adding elements that we’ve already added before…

For ([-3, 2, 3, -1, 5, 1], 3) as input, look at the iterations:

i = 0
- Nested j = 0 to j = 2 computes currentSum to -3 + 2 + 3 = 2, updates maxSum
i = 1
- Nested j = 1 to j = 3 computes currentSum to 2 + 3 + -1 = 4, updates maxSum
i = 2
- Nested j = 2 to j = 4 computes currentSum 3 + -1 + 5 = 7, updates maxSum
i = 3
- Nested j = 3 to j = 5 computes currentSum -1 + 5 + 1 = 5

Optimized Sliding Window

Instead of re-adding the same numbers each time,
let’s just keep a running total with a sliding window.

demo/mSS.js

function maxSubarrSum(arr, k) {
  let maxSum = 0;

  // get the sum of the first three numbers to start
  for (let i = 0; i < k; i++) {
    maxSum += arr[i];
  }
  let currentSum = maxSum;

  // starting after the first sum, compute the rest
  for (let i = k; i < arr.length; i++) {
    // current window adds new element and chops off left
    currentSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

Time Complexity: O(N)

Optimized Solution Visualized

The window adds one to the right and subtracts one to the left in each iteration instead of doing a nested loop to recalculate the sums.

Optimized Solution In Depth

For ([-3, 2, 3, -1, 5, 1], 3) as input…

Every iteration uses the currentSum of the last iteration
but slides the window.

i = 0 to i = 2, currentSum and maxSum set to -3 + 2 + 3 = 2
i = 3, currentSum computed 2 + -1 - -3 = 4, maxSum updated
i = 4, currentSum computed 4 + 5 - 2 = 7, maxSum updated
i = 5, currentSum computed 7 + 1 - 3 = 5

Summary

How did we solve maxSubarraySum with sliding window?

We saw the keyword subarray and the fact that it was a min/max problem with O(n^2) solution, which is a great indicator of a sliding window problem.
We kept a sliding window of k elements, on every iteration we added a new element to the right and subtracted a new element to the left, thereby sliding the window along.
We improved the time complexity from O(n^2) to O(n)
with constant space.