The Polymathic Engineer

Share this post

Sliding Window

newsletter.francofernando.com

Sliding Window

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

Franco Fernando
Nov 21, 2022
5
2
Share this post

Sliding Window

newsletter.francofernando.com

Hello Friends,

Thanks for reading The Polymathic Engineer! Subscribe for free to receive new posts and support my work.

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.

Twitter avatar for @Franc0Fernand0
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}
3:07 PM ∙ Nov 16, 2022
5Likes1Retweet

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

Twitter avatar for @intelocode
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 👇
Image
1:33 PM ∙ Nov 14, 2022
28Likes3Retweets

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.

Twitter avatar for @LBacaj
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.
11:08 PM ∙ Nov 10, 2022
231Likes17Retweets

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.

Thanks for reading The Polymathic Engineer! Subscribe for free to receive new posts and support my work.

2
Share this post

Sliding Window

newsletter.francofernando.com
2 Comments
Greg Lim
Writes Greg’s Newsletter
Nov 26, 2022Liked by Franco Fernando

Lovely Fernando. Loved this format much more than in threads (but both are still good!)

Expand full comment
Reply
1 reply by Franco Fernando
1 more comment…
TopNewCommunity

No posts

Ready for more?

© 2023 Franco Fernando
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing