Sliding Window

How to effectively use the sliding window technique to solve coding interview questions.

Franco Fernando

Nov 21, 2022

Hello Friends,

welcome to the second issue of The Polymathic Engineer newsletter. This week we will focus on the following topics:

the sliding window algorithm
amortized analysis for the sliding window
variants of sliding window algorithm
coding interview question challenge
two interesting tech twitter’s tweets

Sliding Window

The sliding window is a standard method for solving coding problems related to arrays and strings. It comes in very handy for coding interviews.

A sliding window is a subarray that moves from left to right through an array. The window is defined by 2 pointers representing its left and right bound. The nature of the problems usually depends on how is the window size.

If the window size is fixed, the goal is usually to efficiently calculate some information about the elements inside the window. On the other hand, if the window size is variable, the goal is to efficiently find the best window fitting some constraint.

On Twitter, I already provided an example of applying the technique using a fixed-size window.

Fernando 🇮🇹🇨🇭 @Franc0Fernand0

Suppose we have an array of n integers and a window's size. The goal is to maintain and report the smallest value inside each window as this moves. The brute force solution would be to inspect each window, which implies a lot of repeated work. {4/7}

Let's now consider another example where the window size is variable, like the problem Max Consecutive Ones III I solved recently on Leetcode. Given a binary string s (a string containing only "0" and "1"), the problem asks to find the maximum number of consecutive "1" 's in the array after flipping at most k "0" 's.

The brute force solution would be to inspect all the possible substrings, checking which is the longest substring containing at most k "0". But this is clearly inefficient since those subarrays overlap, and a lot of repeated work is done.

Luckily the sliding window method comes to the rescue. The idea is to track how many "0" 's are currently in the window and ensure that the window never includes more than k "0" 's. The right pointer expands the window at each step. The left pointer shrinks the window when the number of included "0" 's is greater than k.

Here is the Python code with the solution:

Amortized analysis

The time complexity analysis of such a problem can be tricky for beginners. Indeed, a while loop inside the for loop could push you to assume that the time complexity is quadratic. But the time complexity is still linear because the while loop can only iterate n times for the entire algorithm. The left pointer starts at 0, only increases, and never exceeds the input's length. This is a case of amortized analysis. Even if, in the worst case, a while iteration inside the for loop is O(n), it averages out to O(1) taking into account the entire runtime of the algorithm.

Number of valid windows

A class of sliding window problems asks not for the best window fitting a constraint but the number of subarrays matching that constraint. The key to solving this problem is to find how many valid subarrays end at each index. This is not hard to answer since it corresponds to the window‘s length after reaching that index. For example, if the window is [1,2,3], the valid subarrays ending at 3 are: [3], [2,3], [1,2,3]. Once you know how many valid subarrays end at each index, you need to sum them up to get the answer to the problem.

Coding Interview Question

For the next week, I challenge you to solve the Subarray Product Less Than K problem using the sliding window technique. I’ll provide the solution in the next newsletter issue.

Two Interesting Tweets

Abhishek Verma 💻 @intelocode

Critical thinking is something that's talked about often, understood by few and practiced by fewer ! A great way to start working on it can be through well renowned Socratic Method. It's a really powerful tool that you should add to your thinking toolbox. Let's explore 👇

Thinking critically and asking the right questions can help you move from blindly accepting the information to analyzing it. Everyone who works as a software engineer needs to be able to think critically. Abhishek wrote a great thread to help you learn and use critical thinking in your work.

Louie Bacaj @LBacaj

Tech is taking a beating. Is a career in tech worth pursuing anymore? Coding & Tech were my way out of poverty. And I’m still a big believer in it changing lives. But while talking to some recently laid-off friends, I had some thoughts on tech careers.

This thread takes the cue from the current situation of layoffs in tech companies, analyzing if it is still worth pursuing a career in tech. There are still plenty of opportunities for developers, especially if they look at something different than big tech. Not to mention that after gaining experience and knowledge, developers have everything needed to start their own businesses.