Sliding Window Technique + 4 Questions - Algorithms

[@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.

[@velvetinskin6567]

Oh thank goodness… I was about to pull my hair trying to figure out how to solve it in O(1) space complexity!

[@fionamatu4996]

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!

[@08JuHan]

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

[@praveensidda9946]

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

[@user-ov5nd1fb7s]

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;}.

[@QuanticDev]

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".

[@cesaredecal2230]

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

[@QuanticDev]

I will. Thanks!

[@AnandKumar-kz3ls]

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

[@benz6234]

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.

[@QuanticDev]

I'm now producing one for Fibonacci puzzles with many questions in it. Enjoy!

[@simonruber5419]

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.

[@keerthivasan764]

Bro do you find solution for second one?

[@soufianeaouri6205]

@@keerthivasan764 here is a solution

[@TeomanSoygul]

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.

[@TeomanSoygul]

@@keerthivasan764 You can easily apply Kadane's Algorithm to solve the second question variant that has negatives in it: kzbin.info/www/bejne/apTWcqateNCLkK8

[@RiteshKudalkar]

It still doesn't work. It fails to capture the window [5].

[@AlexA-vo8bk]

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

[@shantanugaware8780]

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

[@bronzebond4869]

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

[@QuanticDev]

My pleasure. Blogging/vlogging is always like this. It starts very slowly and eventually takes off.

[@PeterParker-sy9bp]

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

[@QuanticDev]

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!

[@siddhantsharma7369]

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

[@QuanticDev]

I will do it next month. Good luck in the interviews.

[@abdullahshoukat7848]

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

[@vanshajsharma3306]

that was best 28 minutes of my day

[@JamesBrodski]

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

[@shreelakshmi6890]

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

[@aliadel1723]

Awesome we need more videos like this for backtracking and prefix sum etc

[@munemadil443]

Great video! One question, why is the space complexity in question 1 constant? For question 2, you said in the worst case we are storing n-windows which makes sense. But aren't we storing n/2 windows in question 1 which by asymptotic equivalence is O(n)?

[@nithinthota96]

Great Explanation!

[@tvnathreviews]

14:37 If you have watched FRIENDS 😁 Great video, thanks...

[@souravde6116]

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.

[@kaushik.aryan04]

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

[@slavaslava9763]

I think there is mistake in Question 2 - Kardane's algorithm used for finding maximum number, not exact number.

[@priyankareddy7408]

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

[@QuanticDev]

No worries, I have a ton of upcoming Google/Facebook interview questions.

[@teqwonnorman3588]

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.

[@shaileshkaiwart7190]

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.

[@jasper5016]

Fantastic, wish you could have shown Java code to represent how to think through code. Thanks again

[@shivamlokhande4856]

at 17:30 , I didn't understand - what do we have to do after adding a positive number

[@michaelsundarev5818]

Thank you. Very easy to understand video.

[@imaginecodes2382]

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.

[@kamalkunjapur5383]

Brilliant video. Thank you so much for making such amazing content.

[@BoTian]

O(n^2) is quadratic time complexity, not exponential. Exponential would be something like O(2^n)

[@QuanticDev]

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!

[@hengzhang5587]

Very good tutorial with good cases. Thanks.

[@vishakamohan5336]

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!

[@QuanticDev]

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.

[@vishakamohan5336]

@@QuanticDev Oh yes. Thank you ! This is a really helpful video, thanks a lot!

[@gabrielasalvo7080]

Amazing explanation!

[@jinny5025]

I just subscribed your channel. Thanks for the helpful materials :) I'm expecting your upcoming videos already!

[@QuanticDev]

My pleasure. I'm switching to fully animated algo videos so upcoming ones will be interesting.

[@damaroro]

Wow your explain is so good, please do upload more about algorithm to solve code challanges

[@deepkakadia5679]

Great Content, very well explained

[@SandeepVarunKoduri]

You just earned a Sub !! Can we please have Java code samples ?

[@QuanticDev]

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.

[@codingwithanonymous890]

thanks for the video u have explained very well

[@大盗江南]

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

[@ayushrawat4825]

You got me subscribed man! really nice video

[@kaushik.aryan04]

please make more videos on dynammic programming and graphs

[@manle4454]

Thanks for this video

[@subhadipadhikary270]

Make a detailed video/series on DP and backtracking or release a course somewhere else

[@viswanathank2551]

Good job bud

[@yehudacorsia3323]

Thank you! its a great video :-)

[@mukarramhaq3663]

Amazing video! You just earned a sub ! :)

[@AccerAspire]

Thank you sir

[@shohanur_rifat]

Subscribed

[@lordmoriartea7799]

can we use this in python?

[@QuanticDev]

Of course

[@huyvole9724]

We need algorithm sliding windows.

[@QuanticDev]

Link to it is in the video description.

[@huyvole9724]

@@QuanticDev you need using algorithm process loss package

[@huyvole9724]

@@QuanticDev arq, ...

[@chuongnguyennguyen2227]

hi

[@nono-qv4um]

teoman 4. soruyu da mulakatta sorarlarsa birakir giderim kardesim

[@QuanticDev]

Heh, no no, that's my exaggeration. It could be in a senior CS course final though.

[@mehdi-vl5nn]

Damn, the video is too old. I hope you see this comment. I wonder what the difference is between an algorithm and a technique?

[@rudranarayansamal4168]

Great Video ! Thanks for the detailed explanation

[@tythedev9582]

This is perfect. Thank you. Subbed