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.
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!
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
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;}.
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.
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.
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: th-cam.com/video/4csAswCkXZM/w-d-xo.html
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
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
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!
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.
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.
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)?
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.
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.
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!
Kudos on wrapping up both sliding window and interview tips in the same video. Thanks a lot for posting it!
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!
Some really really high quality content here. Thank you! I hope you will continue to upload more algorithm videos.
I will. Thanks!
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
Bro had 4K quality uploaded, yet I watched entire video(up till tips section) in 360P without even noticing it💀
thank you so much. you deserve much more subscribers and views.
this is top tier explanation i used to apply sliding window blindly never know the rules thanks bro
You deserve million subscribers, your content is gold, with detailed explanation. Thank you
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".
Awesome we need more videos like this for backtracking and prefix sum etc
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!
Great Explanation!
that was best 28 minutes of my day
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: th-cam.com/video/4csAswCkXZM/w-d-xo.html
It still doesn't work. It fails to capture the window [5].
wow you really explained it very well and fast too just what I was looking for
Thank you so much for making this video! This is beautifully explained.
Very good way of explaining the concept and the problems...It helped a lot!
Keep it up!
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.
Great content. Thanks for explaining so well. Pls upload more algorithm questions.
No worries, I have a ton of upcoming Google/Facebook interview questions.
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.
Very good tutorial with good cases. Thanks.
Thank you. Very easy to understand video.
You got me subscribed man! really nice video
Amazing explanation!
thanks buddy, this video is so good.... so much help!
Great Content, very well explained
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!
Brilliant video. Thank you so much for making such amazing content.
14:37 If you have watched FRIENDS 😁
Great video, thanks...
Great Video ! Thanks for the detailed explanation
Wow your explain is so good, please do upload more about algorithm to solve code challanges
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.
Fantastic, wish you could have shown Java code to represent how to think through code. Thanks again
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.
thanks for the video u have explained very well
Good job bud
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.
please make more videos on dynammic programming and graphs
at 17:30 , I didn't understand - what do we have to do after adding a positive number
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.
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)?
Amazing video! You just earned a sub ! :)
Thank you! its a great video :-)
Thanks for this video
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.
I think there is mistake in Question 2 - Kardane's algorithm used for finding maximum number, not exact number.
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!
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!
Make a detailed video/series on DP and backtracking or release a course somewhere else
Thank you sir
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.
We need algorithm sliding windows.
Link to it is in the video description.
@@QuanticDev you need using algorithm process loss package
@@QuanticDev arq, ...
can we use this in python?
Of course
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.
Damn, the video is too old. I hope you see this comment. I wonder what the difference is between an algorithm and a technique?
hi
This is perfect. Thank you. Subbed