Sliding Window
Another powerful software design pattern is sliding window pattern.
The Sliding Window pattern is defined by creating a 'window' which can either be an array or number formed over some part of the data. This window can slide over the data to capture different portions of it. Depending on a condition, the window either increases or closes (and a new window is created).
Implementation
To understand the multiple pointers pattern implementation, lets first look at the problem Max Subarray Sum,
/**
* Write a function called maxSubarraySum(arr, n) which accepts an array of integers
* and a number n. The function should calculate the maximum n consecutive
* elements in the array.
*
* maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3)
*
*/
This is a perfect problem to solve using a sliding window!
We want to find the max sum of n consecutive elements in the array.
First we check our input and define maxSum ,tempSum to hold our calculated sum. Then we loop up
to n calculating the current max sum. Next we implement our sliding window. We define another loop starting
at n and going to the end of the array. In this loop we will find the max sum by adding the element at the
current index and subtracting the first value in our window. We will also compare maxSum,
tempSum finding the max.
function fastMaxSubarraySum(arr, n) {
if (arr.length < n) return null;
let maxSum = 0;
let tempSum = 0;
for (let i = 0; i < n; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
// This is our sliding window!
for (let i = n; i < arr.length; i++) {
tempSum = tempSum - arr[i - n] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
Use Cases
- When a subset of data needs to be found in array / string / etc..
- Find the longest sequence of unique characters
Code Challenges
Listed below are some of the coding challenges that can be solved using the sliding window pattern. Linked are solutions to each problem on my GitHub. I recommend trying to solve each problem with out looking at the solution first. Good luck!
