QuanticDev

QuanticDev's Engineering and Software Development Resources

View on GitHub

Sliding Window Technique

Sliding Window Technique is a method for finding subarrays in an array that satisfy given conditions. We do this via maintaining a subset of items as our window, and resize and move that window within the larger list until we find a solution. Sliding Window Technique is a subset of Dynamic Programming, and it frequently appears in algorithm interviews. In this article, you will learn how Sliding Window Technique works (with animations), tips and tricks of using it, along with its applications on some sample questions.

In the article, you will find the solutions to the following questions, as well as their time and space complexities:

Table of contents:

Resources

You can find the video narration of this article on YouTube: https://www.youtube.com/watch?v=jM2dhDPYMQM

Video has additional tips and illustrations. If you want to read the comments or leave a comment, do so under YouTube video. If you want to contribute to the article, make a pull request on GitHub.

Overview

Sliding Window is one of the essential Dynamic Programming techniques. It is also one of the common algorithm questions in programming interviews. Any software engineer will have to deal with some form of a sliding window of data at some point in their careers, starting with the job interview of course! It is essential to have an in-depth understanding of algorithms since competitive companies tend to ask more varied and harder questions. If you have a great knowledge of different classes of algorithms, you can apply them to many variations of common interview questions easily.

Sliding Window Technique is a method for finding subarrays in an array that satisfy given conditions. We do this via maintaining a subset of items as our window and resize and move that window within the larger list until we find a solution.

Sliding Window Technique is a subset of Dynamic Programming. Dynamic Programming is a method for simplifying complicated problems by breaking them down to simpler sub-problems. If you can find a sub-problem with a solution that can be applied to the bigger problem, you can solve the bigger problem by solving the sub-problem. In our case, maintaining a subarray window that satisfies the problem constraints is our sub-problem. Moving that window over the entire data will solve our bigger problem.

Sliding Window Technique frequently appears in algorithm interviews since Dynamic Programming questions are the favorites of interviewers. Sliding Window Technique solutions have a time complexity of 𝑂(𝑛), which is linear time, and space complexity of 𝑂(1), which is constant space.

Sliding Window Technique is mostly used for finding subarrays inside larger arrays. You can apply Sliding Window to majority of minimum/maximum/common subarray/substring type of questions. Note that some subarray related questions have very specific and optimized solutions, like that of Kadane’s Algorithm. We will investigate this situation while solving our problems.

How Does It Work?

Let’s see how the Sliding Window Technique works on a sample question. Given an array [1, 2, 3, 4, 5, 6, 7, 8, 9], we will try to find the subarrays that add up to 9. We will start by creating a sliding window from the first two array elements: [1, 2]. This only adds up to 3 so let’s expand the window by one from the right: [1, 2, 3]. The new window still only adds up to 6, so we will expand the window once again: [1, 2, 3, 4]. This new window now adds up to 10, which is bigger than our target of 9. So, we will continue by shrinking the window by one element from the left: [2, 3, 4]. This window now adds up to 9, which is our target. We can continue to expand the window when it is less than or equal to 9 and shrink it when it is above 9, and continue to find rest of the subarrays that add up to 9. And this is basically how the Sliding Window Technique works. Let’s move onto some real-world interview questions to examine harder problems.

Video Solutions

If you want video solutions for the below questions, visit the YouTube link in the resources section. The video has a lot more in-depth info on solution techniques along with helpful visuals.

Easy: Statically Sized Sliding Window: Given an array of integers, find maximum/minimum sum subarray of a given size

Example Input: [-1, 2, 3, 1, -3, 2] - Subarray Size: 2

Requirements:

Analysis:

Approach #1: Brute Force

Approach #2: Sliding Window (Statically Sized)

Tips!

Medium: Dynamically Sized Sliding Window: Given an array of positive integers, find the subarrays of integers that add up to a given number

Example Input: [1, 7, 4, 3, 1, 2, 1, 5, 1] - Desired Sum: 7

Requirements:

Analysis:

Approach #1: Brute Force

Approach #2: Sliding Window (Dynamically Sized)

Example Input: [-1, -4, 0, 5, 3, 2, 1] - Desired Sum: 5 Approach #1: Brute Force

Medium: Flipping/Swapping: Given an array of 0’s and 1’s, find the maximum sequence of continuous 1’s that can be formed by flipping at-most k 0’s to 1’s

Example Input: [0, 1, 0, 1, 0, 0, 1, 1] - Max Flips (k): 2

Requirements:

Analysis:

Approach #1: Brute Force

Approach #2: Sliding Window

Hard: Strings: Given a string and n characters, find the shortest substring that contains all desired characters

Example Input: fa4chba4c - Desired Characters: abc

Requirements:

Analysis:

Approach #1: Brute Force

Approach #2: Sliding Window

Tips!

Coding interview measures if you are going to: