Sliding Window Technique Explained

8 min readApr 25, 2023

The sliding window technique is a continuation of the two pointer technique, which uses two pointers to act as boundary points for a fixed-size segment, i.e “window”, that moves along the data structure performing some operation to obtain a desired result. The operation(s) and size of the chunk rely on the problem statement. The sliding window technique is a computational method aimed to reduce time complexity and number of nested loops, therefore boosting efficiency. To better understand this concept, let’s take a deep dive and go over an example together.

Fig. Sliding Window Technique Visualized (Fixed Window Size)

Overview

The sliding window technique uses two pointers to set up a bounded segment, the “window”. This “window” is a sublist of elements formed over an iterable data structure such as an array or list. Unlike the two pointer technique which isolates two individual points, the sliding window technique encapsulates a set of elements between two points. The sliding window technique can either use a window size that is fixed or variable. During each iteration, there is an operation or series of operations being done to the given chunk. This computation will continue each iteration. This concept is primarily based on ideas such as shortest or longest sequences given to a subset of a given array or list. It is often used to reduce the time complexity of the problem from O(n²) to O(n).

How do I recognize the pattern?

Questions to ask yourself when reading the problem statement can include:

Does this problem involve an iterable data structure that is an array, string or list (i.e., a data structure that is ordered/iterable)?
Are you looking for a chunk or subrange of the given data structure?
Is the naive approach (i.e., brute force solution) time complexity O(n²) or O(kn)?
Does the question involve key words like “optimal”, “longest”, or “shortest” in a sequence of something that requires an exact condition.

How do I use the Sliding Window technique?

The sliding window algorithm can be solved generally with the following steps:

Identify window size by initializing two pointers at the border of the window (Ask Yourself: Is it a fixed or variable size?)
Iterate over the data structure and check the condition(s) as you move the window each iteration
Update the window size as necessary

def sliding_window(nums):
  # iterate over elements in the input array
  # check condition, expand if necessary
    # evaluate current window
    # contract window

Initialize two pointers: one that starts at index 0 and another that is some distance away (i.e., this is our window size). Find the size of window on which the algorithm will be performed (Ask: Is it a fixed or variable size?)
Calculate the result of the first window frame, identify the naive pattern
Loop over each iteration, moving the sliding window by updating the pointer(s) and keeping track of the results of each iteration
Check the condition(s) each iteration: either increase window size and/or proceed OR the condition is NOT met in the given iteration

Note that the window size can either be fixed size or of variable size. See the example gifs below for reference:

Let’s run through an example

I learn the best when I go through an example so let’s try one together. Today we will be covering Longest Substring Without Repeating Characters from LeetCode using the sliding window technique.

PROMT: We are given a string s and we are asked to find the longest substring without repeating characters.

We will be using the input string s where s = "abcabcbb". The output is equal to a length of 3.

Let’s try to pick this apart for a second. The buzz words in the problem statement mentioned “longest substring” and some condition(s). This should ring a bell in your mind, triggering you to say “Aha! This problem requires sliding window technique.”

Notice that the problem statement did not provide a static window size, which means that our window is dynamic / of variable size. We will need to initialize two pointers: one at the head of the data structure and one that travels during each iteration.

We will need to devise a way to keep track of the elements that we have already seen. Let’s use a hashmap (i.e., in Python it’s referred to as a “dictionary”) to store each character as a key and the value is the respective index in the [key : value] pair.

We need to make a list of the possible edge cases. For example, in the string s where s = "abcabcbb" we can continue adding each character to the hashmap one at a time. We don’t run into a duplicate element in the hashmap until we reach index 3, which means we need to adjust our window.

Since the problem statement requires us to return the length of “longest substring without repeating characters” — in other words we need to have a contiguous window. Whenever there is a duplicate element, we need to move Ptr 1on the left up by one. This will be a necessary check.

For each iteration we will do a check, then increment the right pointer, Ptr 2, by 1 until we reach the length of the string s. Keep in mind that our goal is to achieve the longest substring. Once we’ve gone over all elements in the string, we can return the maximum length.

Now that we have a basic idea of what to do, let’s try to explain our approach using pseudocode.

# Pseudocode
def lengthOfLongestSubstring(self, s: str) -> int:
  # Create 2 pointers where ptr1 = index 0 and ptr2 expands the window size
  # Create a hashmap to store seen values --> key/value : character/index

  # Iterate over the all elements in the string s
      # Check if the element is already in the hashmap
      # if it is, update the LHS pointer by moving it left by 1
  # Add element to seen hashmap
  # Increment the window size by one
  # Return the maximum length of the largest substring

Code Implementation

We have a clear idea of how to tackle this problem, let’s code it up!

def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # Create pointers for each end of the window
        left = 0
        max_len = 0

        # Create a hashmap --> key/value : character/index
        seen = {}

        # Iterate over the all elements in the string s
        for right in range(len(s)):
          # check if the element is already in the hashmap
          if s[right] in seen:
            # if it is, update the LHS pointer by moving it left by 1
            left = max(left, seen[s[right]] + 1)

          # add the new element to the hashmap
          seen[s[right]] = right
          # increment the window size by one
          max_len = max(max_len, right - left + 1)
        
        # return the maximum length of the given substring
        return max_len

We can see this in action in the given animation below. The maximum contiguous length that we can achieve with this string is a length of 3.

Recap

To find the length of the longest substring without repeating characters in a given string:

Initialize two pointers, left and right, to mark the start and end of the current window. Start with left and right at index 0.
Create an empty hashmap, seen, to store the characters in the current substring and their indices.
While right is less than the length of the string:

Check if the character at the right index is already in seen.
If the character is not in the hash seen, add it with its index to the hashmap, and increment right.
If the character is already in seen, update left to be the maximum of its current value and the index of the character in the seen plus 1. This removes the old character from the dictionary and updates the new character with its current index.

After each iteration, update the length of the longest substring by taking the maximum of the current length and the difference between right and left plus 1.
Repeat steps 3–4 until right is equal to the length of the string.
The final result is the length of the longest substring without repeating characters.

Other Variations

There are many different methods for the sliding window algorithm (note that these are not all-inclusive):

Fixed Size Sliding Window: In this variation, a fixed-size window is moved over the input array or string, and the result is calculated for each window. This approach is useful when the size of the window is fixed, and the result needs to be computed for each subarray of the given size.
Dynamic Size Sliding Window: In this variation, the size of the sliding window changes dynamically based on some condition. For example, if we are given an array of integers and we want to find a subarray whose sum is equal to a target value, we can start with a window of size 1 and keep increasing the window size until we find a subarray whose sum is equal to the target.
Two Pointers Sliding Window: In this variation, two pointers are used to maintain a sliding window. One pointer represents the start of the window, and the other pointer represents the end of the window. The window is moved by incrementing the end pointer, and if the condition is not satisfied, the start pointer is incremented until the condition is satisfied again.
Multiple Sliding Windows: In this variation, multiple sliding windows are used to solve a problem. For example, if we are given two arrays A and B, and we want to find all the common elements between the two arrays, we can use two sliding windows, one for array A and one for array B, and move them together until we find a common element.