LeetCode Meditations — Chapter 3: Sliding Window
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-03-09 16:04:49

Now that we're familiar with the [Two Pointers technique](https://rivea0.github.io/blog/leetcode-meditations-chapter-2-two-pointers), 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 {% katex inline %} k {% endkatex %}-sized subarray, sliding window is an appropriate technique to use.

For example, getting the maximum subarray (of size {% katex inline %} k {% endkatex %}) sum of a given array can be done like this:


![Sliding window fixed](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hjgv577x34iu2d7polee.gif)

Note that the window size is {% katex inline %} k {% endkatex %}, 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`:

```typescript
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:_

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

_Since the [postfix operator](https://www.programiz.com/article/increment-decrement-operator-difference-prefix-postfix) 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](https://leetcode.com/problems/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:


![Sliding window dynamic](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dvr4q5gxco6ee4q2xjgl.gif)

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

The solution looks like this:

```ts
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;
};
```

| Note |
| :-- |
| This one is also called **fast/catch-up** version of dynamic sliding window, because the `left` pointer jumps to catch up with the `right` pointer in the `else` block. |

##### Time and space complexity

Both examples have the same time and space complexity: The time complexity is {% katex inline %} O(n) {% endkatex %} because in the worst case we iterate through all the elements in the array. The space complexity is {% katex inline %} O(1) {% endkatex %} 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](https://leetcode.com/problems/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.