Sliding Window Technique

Resources:

1. Video explanation
2. Leetcode problem

Takeaways:

• The sliding window technique is where we use two pointers on a collection. We say that one pointer represents the start of the window and the other the end of the window. The space/elements between the two pointers is the window size.
• A sliding window can be of fixed length or it can be variable length (meaning the window expands/contracts dynamically).
  • Fixed length is often easier to grasp/think about. Both pointers, say i and j, in a loop are incremented by the same number each time our max window size is reached.
  • Variable length is where i or j change at a different pace to each other. Often questions requiring this technique don't provide a window size, but ask for the largest/smallest possible window given some constraints.
• Here are some questions we can use the sliding window technique on:
  • In an array of n integers, find a contiguous k length subarray that has the largest value when it's elements are summed.
    • We can use two pointers here and our window would be of size k.
  • What is the size of the minimum subarray that when summed will equal a target sum?
    • We can use two pointers here, but because we want the minimum length subarray (i.e the question is asking how big/small the window is) the window can't be of fixed length.
  • What is the largest subarray of k distinct characters?
    • We can use two pointers here. This will again be a variable length window, as we are being asked what the size of the window is (largest subarray). We will also need to use an auxiliary data structure to keep track of how many distinct characters are in a given subarray.
• A less obvious question where sliding window would come in handy:
  • Given two strings inputA & inputB, determine if any permutation of inputA is a substring of inputB.
    • Here we can use two pointers and the window will be of fixed size/won't ever grow larger than the length of inputA.

Below are solutions to all the problems mentioned. I have annotated the source code with time & space complexities for each solution:

As always, if you found any errors in this post please let me know!