How to Solve Sliding Window Problems Faster

When you encounter array and string problems that you can't solve because your solution takes too long, it's like hitting a wall. If you struggle with inefficient nested loops while solving array or string problems, you may not yet be familiar with sliding window problems.  In this article, you will learn about the sliding window problem thoroughly and will be able to recognise the pattern instantly and be able to implement the most efficient solution every time.

What Are Sliding Window Problems?

The essence of the sliding window is an optimisation technique that converts a nested loop (quadratic time) into a single loop (linear time). It's sort of like a camera lens moving across a landscape, and you only care about what is within the frame at the moment that you're looking at it.

A sub-segment of data in an array or string that forms this "frame" is a part of the coding interview problem. The window slides from left to right, adding a new element to its right and removing an old one from its left. This technique will save you a lot of time when computing the sum or property of the entire window, as it will not be necessary.

How to Identify Sliding Window Problems

Determining when to employ this tactic is one of the difficulties developers face while solving coding interview problems. Seek out the following 3 warning signals in a problem statement:

1. The Input Type: An array, string, or linked list are examples of linear data structures.

2. The Goal: To find a subarray (vector), subsegment (segment), or substring that has some property (maximum sum, minimum length, etc.) or is the longest, shortest, or most unique substring or substrings in some other way.

3. The Constraints: A condition or fixed length of k is provided in the problem. When brute force would involve checking all possible subarrays, you are definitely dealing with a sliding window problem. When you are looking for “longest”, “shortest”, or “contains”, you are in the sliding window.

In this blog post, I’ll discuss three approaches to solving sliding window problems faster.

How to Solve Sliding Window Problems 

These techniques will help you to avoid getting stuck during an interview. Follow this step-by-step mental structure:

Step 1: Initialize Your Pointers

Place the left and right arrows at the start of the array (index 0). Begin to keep a variable to track the state of your window (e.g., current_sum or a hash_map of character count). Initialise a variable to keep track of the state of your window (e.g., current_sum or a hash_map to keep track of the count of the characters).

Step 2: Expand the Right Boundary

Move the right pointer forward by using a loop. As you add this new element to your window state, also add it to your window state. This expands the current window.

Step 3: Shrink the Left Boundary 

If the window is variable, determine whether it satisfies the condition in the problem. If it does, then "remove" the element at the left pointer and move the left pointer to a smaller window.

Step 4: Record the Result

As you make each valid step, add to the global maximum or minimum. This way you'll be able to get the maximum possible answer after the appropriate pointer arrives at the end of the input.

Sliding Window Problem Examples

Let's consider an example. Let's take an actual case study of how the DSA sliding window technique works.

Problem: Given the array and k = 3, find the maximum sum of any subarray of k = 3 contiguous elements. Input Array: [2, 1, 5, 1, 3, 2]

The Brute Force Approach (The Slow Way)

The beginner could attempt to get all combinations of length three:

1. [2, 1, 5] -> Sum = 8

2. [1, 5, 1] -> Sum = 7

3. [5, 1, 3] -> Sum = 9

4. [1, 3, 2] -> Sum = 6

This means having to add the numbers up again for each case and each window. The more elements there are in the array, the more times this addition will repeat itself.

The Sliding Window Approach (The Fast Way)

Now we simply "slide" the window, instead of re-adding

1. First Window: [2, 1, 5]. Total Sum = 8.

2. Slide Right: Go to the next element (1). We do not add 1 + 5 + 1; instead, we take the sum already in the window (8), remove the element that has been removed from the window (2), and add the element that is entering the window (1).

• Calculation: 8 - 2 + 1 = 7.

3. Slide Again: The sum of the previous slide was 7. Subtract 1 (left side) and add 3 (right side).

• Calculation: 7 - 1 + 3 = 9.

4. Final Slide: The sum was 9 the last time. Add 2 (right side) and subtract 5 (left side).

• Calculation: 9 - 5 + 2 = 6.

We used only 2 operations (subtracting and adding) per step and got the maximum sum (9) in linear time. When interview time is limited, efficiency is essential for solving problems.

How to Improve Sliding Window Problems

It's the first step, but the second step is to make your implementation as effective as possible. A few of the more advanced tips:

Use Hash Maps for Substring Problems

When you need to work with strings and unique characters, a hash map (or an ASCII array of size 256) is the most useful data structure. It lets you save the frequency of characters in the current window. It is obvious that when the frequency is > 1, you need to start reducing the size of the left pointer.

Use deques for maximums in windows.

A simple sliding window does not suffice for problems such as "finding the maximum of each subarray of size k". You can use a double-ended queue (deque) to store the index so that the largest value is always at the front, thus maintaining a very rapid solution.

Handle the "Initial Window" Separately

In fixed-size problems, calculate the state of the first window (index 0 to k-1) prior to the main loop. This improves the primary loop, making it easier to avoid index errors.