LeetCode Meditations — Chapter 3: Sliding Window

Now that we're familiar with the Two Pointers technique, we can add another one to our toolbox: the Sliding Window.
It's usually used for operations done on the subsets of a given data. It also comes in two flavors: fixed window size and dynamic window size.

Fixed window size

If we have a size constraint in a given problem, say, we need to check a $k$ -sized subarray, sliding window is an appropriate technique to use.

For example, getting the maximum subarray (of size $k$ ) sum of a given array can be done like this:

Note that the window size is $k$ , and it doesn't change throughout the operation, hence, fixed size.

A very cool thing to notice here is that with each slide, what happens to our sum is that we add the right element, and decrease the left element.

Let's look at an example for getting the maximum sum of subarray with given size k:

function maxSubarray(numbers: number[], k: number) {
  if (numbers.length < k) {
    return 0;
  }

  let currentSum = 0;

  // Initial sum of the first window 
  for (let i = 0; i < k; i++) {
    currentSum += numbers[i];
  }

  let maxSum = currentSum;

  let left = 0;
  let right = k;

  while (right < numbers.length) {
    currentSum = currentSum - numbers[left++] + numbers[right++];
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

Note that updating the pointers can be done outside the brackets as well, like this:

while (right < numbers.length) {
  currentSum = currentSum - numbers[left] + numbers[right];
  maxSum = Math.max(maxSum, currentSum);
  left++;
  right++;
}

Since the postfix operator returns the value first, they can be used inside the brackets to be slightly more concise.

Here, we first get the initial sum of our window using the for loop, and set it as the maximum sum.

Then we initialize two pointers: left that points to the left end of the window, and right that points to the right end of the window. As we loop, we update our currentSum, decreasing the left value, and adding the right value. When our current sum is more than the maximum sum, maxSum variable is updated as well.

Dynamic window size

As opposed to the fixed window size version, the size of the window changes dynamically this time.

For example, let's take a brief look at the problem Best Time to Buy and Sell Stock that we'll see in detail later on.
We need to choose a day to buy a stock, and sell it in the future. The numbers in the array are prices, and we need to buy the stock at as low a price as we can, and sell it as high as we can.

We can initialize left and right pointers again, but this time, we'll update them depending on a condition. When the left item is less than the one on the right, that means it's good, we can buy and sell at those prices, so we get their difference and update our maxDiff variable that holds the maximum difference between the two.
If, however, the left one is greater than the right one, we update our left pointer to be where the right is at.
In both cases, we'll continue updating right until we reach the end of the array.

With the blue arrow indicating the left pointer, and the red the right one, the process looks like this:

For unoptimized (slower) version of this GIF, see https://rivea0.github.io/blog/leetcode-meditations-chapter-3-sliding-window.

The solution looks like this:

function maxProfit(prices: number[]): number {
  let left = 0;
  let right = left + 1;
  let maxDiff = 0;

  while (right < prices.length) {
    if (prices[left] < prices[right]) {
      let diff = prices[right] - prices[left];
      maxDiff = Math.max(maxDiff, diff);
    } else {
      left = right;
    }

    right++;
  }

  return maxDiff;
};

Time and space complexity

Both examples have the same time and space complexity: The time complexity is $O(n)$ because in the worst case we iterate through all the elements in the array. The space complexity is $O(1)$ as we don't need additional space.

Even though it might be slightly disorienting, sliding window technique is not too hard to fall from our grasp, so we can take a deep breath. The first problem of this chapter is Best Time to Buy and Sell Stock that we already mentioned, but we'll see in detail in the next post. Until then, happy coding.