Mastering the Sliding Window Technique

The sliding window technique is one of the most important for both Coding Interviews and Software Engineering. Learn more about it here-

6 min readFeb 28, 2024

Mini reminder- If you are looking for work (and are eligible to work in the USA), my company is helping with placing people here. To be notified about potential matches for your profile, all you need to do is to fill out your details on this Google Form here, and you will be added to the database. Also, if you are based in NYC and would like to be regularly updated on the NYC Meetups, You can leave your email here.

More details on both of these in this post

The sliding window technique is a powerful algorithmic mental model that can be used to solve a wide variety of problems. These show up somewhat frequently both in coding interviews and in IRL software Engineering. Whether you’re looking to improve your software engineering skills or ace your interviews, this is not an idea you want to overlook. Let’s cover what they are, some benefits, how you can spot them, and more.

What is the Sliding Window Technique?

It involves imagining a window that slides over an array or data structure, looking for a specific condition to be met within the window. Very shocking, given the name, so take a second to come back to reality.

There are generally two types of sliding window questions that you will have to deal with:

Fixed window length k: Here, the length of the window is fixed and it asks you to find something in the window such as: the maximum sum of all windows; the maximum; or median number of each window. Usually, we need variables to maintain the state of the window. These can be as simple as an integer or it could be as complicated as some advanced data structure such as list, queue, or deque.

Image Source

Two pointers + criteria: In such problems, the window size is not fixed and you will usually be asked to find the subarray that meets the given criteria. For eg. the animation below is for the question- “Given an array of positive integers and a positive integer, write a function that returns the minimal length of a contiguous subarray, where the sum is greater than or equal to the integer being passed in. If there isn’t one, return 0.”

Image Source

Benefits of using the Sliding Window Technique:

Reduces duplicate work: Sliding windows only look at the subset of information that is relevant to your challenge. This reduces duplicate work. This is especially true of rolling hashes
Consistent linear time complexity: In many cases, the sliding window technique can be used to solve problems in linear time, which is more efficient than other approaches that might have quadratic or higher time complexity. This consistency in computing the time-complexity of the process can make your life a lot easier for planning (and in high-stress interviews).
Convolutions and Locality- This is specific to AI, but the feature extraction process in CNNs utilizes sliding windows to slide through the image and extract features while imposing locality. Some people mistakenly assume that you can just utilize the features extracted by Vision Transformers, but that is leaving a lot of performance on the table.

How to Spot the Sliding Window Technique:

The problem involves finding a maximum, minimum, longest, or shortest something: These are all common keywords that can indicate that the sliding window technique might be a good fit.
The problem deals with continuous elements: The sliding window technique is well-suited for problems that involve finding something within a continuous sequence of elements.
The problem can be solved with a brute-force approach, but the brute-force approach is inefficient: This is more of a general tip, but remember that there is nothing wrong with going brute-force first and then analyzing the process to see what really causes the inefficiency in your solution. Then you can zero-in on this. Sliding Windows are nice because they

Examples of the Sliding Window Technique:

Maximum sum of a contiguous subarray: This is a classic example of the sliding window technique. The problem is to find the subarray (of a fixed size) within an array that has the largest sum. The sliding window technique can be used to solve this problem in linear time.
Longest substring with K distinct characters: This problem is to find the longest substring within a string that contains no more than K distinct characters.
Minimum window size containing all elements of a target subarray: This problem is to find the smallest subarray within an array that contains all of the elements of a given target subarray.
Rolling Hash: Given their utility in text processing (amongst other use-cases) this deserves a special highlight. Rolling Hashes are a super powerful technique to do pattern matching, and they rely on sliding windows. We covered one such rolling hash, Rabin Karp, in an older piece here.

For those of you that want to prepare for your interview, Substack allows the option to search through the older articles by topics. You can find the pieces we did on Sliding Windows here.

One of the sources that I really liked (and what inspired this article) was the following video. It’s quite long, but to those of who learn better with videos, this might be a valuable source. Would recommend this YouTube channel (Ryan Schachte or The Simple Engineer), it has some really high-quality information for software development. The only unfortunate thing is that he hasn’t posted in a while.

That is it for this piece. I appreciate your time. As always, if you’re interested in reaching out to me or checking out my other work, links will be at the end of this email/post. If you like my writing, I would really appreciate an anonymous testimonial. You can drop it here. And if you found value in this write-up, I would appreciate you sharing it with more people. It is word-of-mouth referrals like yours that help me grow.

Upgrade your tech career with a premium subscription ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and tech industry with expert insights, tips, and resources. 20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!

Using this discount will drop the prices-

800 INR (10 USD) → 640 INR (8 USD) per Month

8000 INR (100 USD) → 6400INR (80 USD) per year

Get 20% off for 1 year