Sliding Window Technique + 4 Questions - Algorithms
Вставка
- Опубліковано 26 чер 2024
- 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:
• github.com/soygul/QuanticDev/...
If you can read the article version of this video at:
• quanticdev.com/algorithms/dyna...
My video describing Test-Driven Development (TDD) and other software patterns:
• • Software Design Patter...
My "Algorithms" Playlist for all other algorithm questions & answers:
• • Algorithms
- - - - - - - - - - -
/ quanticdev
/ quantic_dev
quanticdev.com
- - - - - - - - - - -
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.
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.
Oh thank goodness… I was about to pull my hair trying to figure out how to solve it in O(1) space complexity!
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!
Kudos on wrapping up both sliding window and interview tips in the same video. Thanks a lot for posting it!
Thank you so much for making this video! This is beautifully explained.
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
Some really really high quality content here. Thank you! I hope you will continue to upload more algorithm videos.
I will. Thanks!
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;}.
Haha. These things happen a lot in interviews. Then the interviewers try to modify the question with "oh my bad, let me add some more constraints".
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.
I'm now producing one for Fibonacci puzzles with many questions in it. Enjoy!
Very good way of explaining the concept and the problems...It helped a lot!
Keep it up!
Bro had 4K quality uploaded, yet I watched entire video(up till tips section) in 360P without even noticing it💀
You deserve million subscribers, your content is gold, with detailed explanation. Thank you
thanks buddy, this video is so good.... so much help!
Brilliant video. Thank you so much for making such amazing content.
Thank you. Very easy to understand video.
Very good tutorial with good cases. Thanks.
This is perfect. Thank you. Subbed
that was best 28 minutes of my day
wow you really explained it very well and fast too just what I was looking for
Great Content, very well explained
thank you so much. you deserve much more subscribers and views.
You got me subscribed man! really nice video
this is top tier explanation i used to apply sliding window blindly never know the rules thanks bro
Thank you! its a great video :-)
Amazing explanation!
Hello @QuanticDev, thank you for the tips. There is one thing I noticed, in the last question where you're searching for the substring in a larger string, you said that Space Compx was O(1) but in your code, you are creating a hashmap of characters to their occurrrence counts. So it actually uses O(m) space where "m" is the number of distinct chars in substring. Just wanted to point that out ve video için tekrardan teşekkür ederim :).
You are right on point Pete! Space complexity is O(m). Initially I wrote an O(1) solution but time complexity of that was much higher so I traded some memory for efficiency, and forgot to fix the presentation. Good catch!
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
My pleasure. Blogging/vlogging is always like this. It starts very slowly and eventually takes off.
thanks for the video u have explained very well
Great content. Thanks for explaining so well. Pls upload more algorithm questions.
No worries, I have a ton of upcoming Google/Facebook interview questions.
I just subscribed your channel. Thanks for the helpful materials :) I'm expecting your upcoming videos already!
My pleasure. I'm switching to fully animated algo videos so upcoming ones will be interesting.
Amazing video! You just earned a sub ! :)
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
I will do it next month. Good luck in the interviews.
Thanks for this video
Wow your explain is so good, please do upload more about algorithm to solve code challanges
14:37 If you have watched FRIENDS 😁
Great video, thanks...
please make more videos on dynammic programming and graphs
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.
Bro do you find solution for second one?
@@keerthivasan764 here is a solution
Ah, I should have mentioned it. You don't look for 10, instead you look for 5 + 5 * k, where k is the no of elements in the current window. That would make [0,5] = 15 = 5 + 5 * 2, and it would be valid. As you observed, each time we expand the window, we are adding +5 to the final sum that we are looking for, and -5 each time we shrink the window. Pre-processing arrays like this is sometimes very useful, but obviously a pretty bad solution here.
@@keerthivasan764 You can easily apply Kadane's Algorithm to solve the second question variant that has negatives in it: ua-cam.com/video/4csAswCkXZM/v-deo.html
It still doesn't work. It fails to capture the window [5].
I think there is mistake in Question 2 - Kardane's algorithm used for finding maximum number, not exact number.
Thank you sir
Fantastic, wish you could have shown Java code to represent how to think through code. Thanks again
Good job bud
at 17:30 , I didn't understand - what do we have to do after adding a positive number
You just earned a Sub !! Can we please have Java code samples ?
Thanks. It's a good idea given the persistent popularity of Java. But going forward, I will only use pseudocode as it is one universal language that all developers will understand. Otherwise, people get confused about language primitives of specific programming languages. However, if anyone contributes a solutions in other languages, I will put them on GitHub next to other solutions.
Great Video ! Thanks for the detailed explanation
Why are you not making more videos on algorithm?? Your videos are very very very helpful in understanding an algorithm and its variations.
Please make more videos. These kind of videos are not present in youtube.
In that example of finding the maximum sum of subarray, I did not find any difference you did between brute force approach and sliding window concept except for one you write it on the bottom and for later you write it on top.
Subscribed
22:00 i know for this given ip array there will one answer but lets suppose i took an diff ip array
like [0,1,0,1,0,0,0,1,1] , there will a tie.
I have a doubt regarding the first question maximum sum subarray. I don't understand how the time complexity is O(n). I mean we do have a variable for the start and end indices and sliding this window across the array will have a time complexity of O(n) ,but shouldn't we also consider the time complexity for calculating the sum of the elements between the start and end index? Then wouldn't the time complexity result in O(n^2) instead-- ( O(n) for sliding across and a nested loop for the sum,which is again O(n) )?
Please clear my doubt .Thanks!
No need to recalculate the window sum over and over again. We just keep its current value in memory and add the value of the next element from right, or subtract the leftmost element to move the window. You can see the code for this in GitHub and the link is in the video description.
@@QuanticDev Oh yes. Thank you ! This is a really helpful video, thanks a lot!
I noticed a mistake with the 3rd problem at 16:55. The target sum was 5 but you said the entire array was the first subarray but the entire array added up to 6, and you started shrinking the array getting the next subarray of (3,2) but i got a subarray of (0,5) instead.
Make a detailed video/series on DP and backtracking or release a course somewhere else
O(n^2) is quadratic time complexity, not exponential. Exponential would be something like O(2^n)
True. I have the correction at the top as a pinned comment but I guess it is harder to see on mobiles. Good catch anyway!
can we use this in python?
Of course
We need algorithm sliding windows.
Link to it is in the video description.
@@QuanticDev you need using algorithm process loss package
@@QuanticDev arq, ...
hi
teoman 4. soruyu da mulakatta sorarlarsa birakir giderim kardesim
Heh, no no, that's my exaggeration. It could be in a senior CS course final though.