Algorithm Patterns 101: Sliding Window

The sliding window pattern is used to process sequential data by maintaining a moving subset of elements.

When we first start our algorithm journey our first inclination is to use nested loops. Sliding window is aimed at reducing our habit of using nested loops.

A “window” is a data structure within a data structure; a “sublist” if you will. Once we create this data structure, it can be used to slide over the data in chunks corresponding to the window size.

This algorithm is far more efficient because we iterate over all small “window” instead of an entire the entire data structure O(n).

To create the “window”, we create two pointers (similar to the two pointer algorithm). Another way to describe is to converted two nested loops into a single loop.

Best Uses/Scenarios

• The problem requires repeated computations on a set of elements
• Calculation performed every time the window moves take
• Usually used on arrays or when random access is not allowed.
• Calculating running averages
• If you need to calculate longest, shortest, or most optimal sequence that satisfies a given condition in a collection.

Step-By-Step

Sliding window comes down to these steps:

1. Create the window
2. Expand the window
3. Meet the condition and process window data
4. Contract the window

Before doing any of these steps it’s crucial to stop and think of when to stop!

Calculate Rolling Average / Average Sub Array

It is very common for investors to calculate the rolling average of an asset. Instead of calculating the average of the entire subset, we calculate the average for a specific sets of days! This is sometimes referred to as “Find Averages of Sub Arrays”:

Our algorithm will take in two parameters

runningStockAverage(stocks, period);

Steps:

1. Break down list into sub lists based on period
2. Take the average of each sublist
3. Put the averages together

To build the sub lists, we repeatedly take sub arrays from the list until we hit the end:

Although we can perform any operation, since we want the average, just add up the arrays and divide.

Brute Force Find Rolling Average

A brute-force algorithm will calculate the sum of every 5-element contiguous subarray of the given array and divided the sum by 5 to find the average.

function findRollingAverage(arr, k) {
      const results = [];

      for(let i = 0; i < arr.length - K + 1; i++) {
          let sum = 0;
          for(let j = i; j < i + K; j++) {
              sum += arr[j]
          }
          results.push(sum/K);
      }
      return results
}

This works. But unfortunately this code is O(N)^2 and will not be acceptable in a tech interview.

Sliding Window Approach

Upon further inspection, you will realize that to calculate the rolling average, we can utilize the sum of the previous subarray. Consider each subarray as a Sliding Window of size k and calculate the sum of the next subarray.

function findMaxAverage(arr, num) {
   if(num > arr.length) {
       return null;
   }

   //Delcare our state
   let maxSum = 0;
   let tempSum = 0;

   //Create the window
   for(let i = 0; i < num; i++) {
      maxSum += arr[i];
   }

   tempSum = maxSum;

   //Slide window over the 
   for(let i = num; i < arr.length; i++) {
       tempSum = temp - arr[i - num] + arr[i];
       maxSum = Math.max(max, temSum);
   }

   return maxSum / num;
}

In this example:

• Check is num is greater then the length (our code would not work if this occured)
• Declare the maximum as variable. Technically, you could keep track of these values in the for loop but making variables makes our code more readable.
• Create the window
• Iterate over the rest of the array, sliding the window over from left to right.