Sliding Window Technique + 4 Questions - Algorithms

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 programming interviews, computer science classes, leetcode, etc. In this video, 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 video, you will find the solutions to the following questions, as well as their time and space complexities:

• Easy: Statically Sized Sliding Window: Given an array of integers, find maximum/minimum sum subarray of the required size.
• Medium: Dynamically Sized Sliding Window: Given an array of positive integers, find the subarrays that add up to a given number.
o Variation (Medium): Same question but for an array with all integers (positive, 0, negative). The optimal solution is Kadane's Algorithm, but Sliding Window can still be applied with modifications (not recommended though).
• 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.
• Hard: Strings: Given a string and n characters, find the shortest substring that contains all the desired characters.

0:00 Intro
0:52 Overview
2:24 How Does It Work? (Animated)
3:30 Question #1
9:00 Tips
9:47 Question #2
15:02 Question #2 Variant
17:52 Question #3
22:15 Question #4
26:22 Tips

Solution code to examples are available on:

If you can read the article version of this video at:

My video describing Test-Driven Development (TDD) and other software patterns:

My "Algorithms" Playlist for all other algorithm questions & answers:

- - - - - - - - - - -

- - - - - - - - - - -
Abstract:
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.

[QuanticDev]

12:40 I had "exponential complexity" on screen which should actually read "quadratic (polynomial) complexity" instead.
26:09 The actual space complexity of last question is O(m), where "m" is the number of distinct chars in the "Desired Characters" list. I tweaked my algo a little but forgot to update the space complexity value for the video.

[JuHan]

Kudos on wrapping up both sliding window and interview tips in the same video. Thanks a lot for posting it!

[fionamatu]

I wish we could have more of these kinds of windows which cover techniques applicable for each class of problem. Very helpful for when you need to quickly pick out what method and data structure to use for a scenario. Thank you for this video!

[ovndfbs]

Here is a nice trick question.
Given an array of positive integers, return the maximum subarray.
It's a 1 liner function maxSubArray(arr []uint){return arr;}.

[cesaredecal]

Some really really high quality content here. Thank you! I hope you will continue to upload more algorithm videos.

[shantanugaware]

Bro had 4K quality uploaded, yet I watched entire video(up till tips section) in 360P without even noticing it💀

[praveensidda]

I always had the confusion regarding the sliding window problems, but kudos to your video, it made the sliding concept very clear . the application part is really great

[AlexA-vobk]

You deserve million subscribers, your content is gold, with detailed explanation. Thank you

[AnandKumar-kzls]

this is top tier explanation i used to apply sliding window blindly never know the rules thanks bro

[simonruber]

Thanks so much for sharing :-)!
I think the trick you apply to solve Question 2, (even though you mention that it's not recommended) does not work at all. When adding a constant to all elements, then subarrays of different lengths are affected differently, therefore the structure of the solution changes. E.g. when adding 5 to all elements, (one would search for a subarray with value 10 then I assume). The in the original array valid answer of [0, 5] = 5 would be transformed to [5, 10] = 15 which would not be a valid subarray in the transformed problem.

[bronzebond]

Very surprised to see you have less than 2k subscribers. The size of the following subscribers definitely doesnt note the quality of the content. Thanks for explaining the pseudo code and constraints so well. You've got a new subscriber here

[abdullahshoukat]

thank you so much. you deserve much more subscribers and views.

[benz]

Thanks for this. I really enjoyed the format of this video. That is, explanation of a commonly used algorithm, and how it can be utilized in various levels of difficulties. It helped me understand the use case in each, which helped me recognize patterns of when to use the algorithm. I hope to see more videos in this kind of format.

[kaushik.aryan]

wow you really explained it very well and fast too just what I was looking for

[JamesBrodski]

Thank you so much for making this video! This is beautifully explained.

[shreelakshmi]

Very good way of explaining the concept and the problems...It helped a lot!
Keep it up!

[michaelsundarev]

Thank you. Very easy to understand video.

[priyankareddy]

Great content. Thanks for explaining so well. Pls upload more algorithm questions.

[siddhantsharma]

Sir this was a really helpful video providing deep insight of this technique..It would be really beneficial for me if you can make a video on kadene's algorithm and it's variations that can be asked in technical Interviews

[oykfwrl]

thanks buddy, this video is so good.... so much help!