Sliding Window Maximum | Leetcode
Вставка
- Опубліковано 2 жов 2024
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- SDE sheet: bit.ly/takeUfor...
Watch at 1.25x for better experience ..
✅Use coupon-code "TAKEUFORWARD" for getting 15% for all CN courses: aff.codingninj...
---------------------------------------------------------------------------------------------------------------------------
Problem Link: leetcode.com/p...
C++/Java Code: takeuforward.o...
---------------------------------------------------------------------------------------------------------------------------
✅Use coupon-code "STRIVER" for getting 10% on all subscriptions of Unacademy
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
✅Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
---------------------------------------------------------------------------------------------------------------------------
Products that I use:
Best Mic in Affordable Range: amzn.to/3hiTr9p
Yeti mic: amzn.to/3dL4tDF
Boya mic: amzn.to/3h4ROgy
Logitech webcam: amzn.to/3h7d2KI
Cooling pad: amzn.to/3y46pi4
Wacom pad: amzn.to/3xacSIq
Ring light: amzn.to/3y7aaU1
Mic Arm Stand: amzn.to/3qzMuFa
Digitek Green light stand: amzn.to/2U7B3bI
Digitek Stand: amzn.to/363m7Oo
Tripod: amzn.to/35ZmbyT
Office chair: amzn.to/3qysu5Z
Ipad Air: amzn.to/3hjpiXx
Iphone 12: amzn.to/3AavyJV
Watch: amzn.to/3hn7w5A
Macbook Air: amzn.to/363lSTu
Macbook Pro: amzn.to/3qCczDr
Board: amzn.to/3x8GLIO
Mouse: amzn.to/360Asv1
---------------------------------------------------------------------------------------------------------------------------
✅Placement Series: • Let's give back to the...
✅Placement Series (Arrays, Sorting..): • C++ and Java |Brute-Be...
✅Hashing Playlist: • Two Sum Problem | Leet...
✅Greedy Playlist: • N meetings In One Room...
✅Recursion Playlist: • L8. Combination Sum | ...
✅Graph Playlist: • 3 MAJOR ANNOUNCEMENTS ...
✅Two Pointer Playlist: • 3 SUM | Brute | Better...
✅Binary Search Playlist: • Nth Root of a Number U...
✅LinkedList Playlist: • Reverse a Linked List ...
✅Advanced DS playlist: • Fenwick Tree Tutorial ...
✅Stack&Queue Playlist: • Implementation of Stac...
✅Greedy Algorithms: • N meetings In One Room...
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFam...
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: www.google.com... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
##dsa #striver #leetcode
If you understand it, please do like it, and if possible please spare 2 seconds for a comment :)
make videos on dp please
What's the difference between deque and list?
16:22 smaller than equal to is not ok!!
only smaller than will be ok striver.
i don't know why anyone didn't point this out.
@@PrinceKumar-el7ob It would work. Try some test cases.
The best explanation on sliding window
I got this question in a Microsoft interview for SDE 1
Is it offcampus or oncampus
@@kingmaker9082 Off campus
@@zetro6311 from where u applied for Microsoft or have u got any referral? Plz guide me...btw what is the result of interview bro?
@@kingmaker9082 hello bro? which batch are you?
@@vinyass3733 23 batch
This explanation literally made me overcome my fear of stacks and queues. Thank you so much!
Ya exactly..... I also have fear of stack and queue.. Even though they are quite easy to understand.
How one question can over come your fear? 🤔🤔🤔🤔
Much better explanation than in the new playlist !
Waiting for tree series :)
Please increase the frequency of uploads as this is PLACEMENT SEASON
I don’t get the intuition that whenever we remove leftmost index from our window to go to the next window, why the left most index will also be the left most element in the deque (so we just remove the first element from our deque). In my thinking, I should loop through the deque to find the index to remove for every window.
I couldn't understand this problem's solution even after reading several leetcode discuss posts. However, I understood this completely at once after watching your video! Thanks!
Bhai when your course starts in unacademy pls update waiting for your course
Python simple one
x=[1,3,-1,-3,5,3,6,7]
k=3
y=[]
for i in range(len(x)-2):
y.append(max(x[i:i+k]))
print(y)
kudos to your patience while explaining sir.The way of you instruct the solution to the problem was quite appealing, unlike some other youtubers who just write the code in rush without explaining properly.
Thanks again
bro getting harsh with apna collegeg
Very great explanation. Thank you bhaiya for helping out the students but I have one suggestion pls upload videos on regular basis. I know u are very busy but it will be helpful for students who are appearing in this placement season. We have found the solution of dse sheet from anywhere but the video explanation of yours is very helpful to remember the concepts and do similar type questions on particular algorithms.
Best Explanation. Thank you so much. Finally understood the use of deque for this problem.
directly jumped to solution,
Intution is missing... :(
it is not working for all the test cases in geeks for geeks
This question can also be solve using heap
Such a Nice Explanation even a beginner can understand. Thanks a lot
That definitely not at 5:15 reminds me of Dhoni xD.
*Brute force*
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vectorans;
int n = nums.size();
for(int i=0; i
It is always challenging as well as fun to learn the optimal solution. But, your explanation helps a lot to understand it better.
Hello Striver, new here, can you tell whether you are covering only this SDE sheet here on any other topics too ? anyone ?
I am brining in series shortly..
Can u pls provide me a python soln for it
you are amazing God bless you. I wanna become like you one day
This can also be solved using multiset, can we use multiset in the interview bhaiya?
good explanation, thank you.
UNDERSTOOD..........Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
how is i-k the outbound element? at 16:02 ?
class Solution {
public:
vector maxSlidingWindow(vector&v, int k) {
vector ans;
int i,j;i=j=0;
deque q;
while((i < v.size()) && (ans.size() < v.size() - k + 1)){
while((j
Very good explaination , though i have to see it 2 times to completely understand the concept👍
What a explanation 😯...I think this is the best video of window problem in UA-cam... Thank you so much for this great video....
great explaination as always.... waiting for more videos
can someone please explain to me line 13, why he put if(i >= k - 1) when I will reach 2 in case of k = 3, then for I =4, 5, 6 to will continuously putting element into ans.
Please solve my doubt if someone can.
yeah bcz there will be n-k-1 subarrays so if you just dry run it ,it will start putting the max into the ans vector after the first sub array has traversed,and then after at each i it will store the max value for next respective sub array
so that it can reach the length of subarray
Why we push indices instead of actual elements?
to basically check if that value is within the window of size k
@@adeshsawant9937 That you can check from elements also right?
Can you give any test case where pushing elements will fail?
I tried this question but 40/50 testcase passed, I am here to see whats the mistake I have done
```
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
int i=0,j=0;
vector ans;
priority_queue pq;
if(k>n){
ans.push_back(*max_element(nums.begin(),nums.end()));
return ans;
}
while(j
Respect for Aditya verma increased after this lecture 🙇♀️🙇♀️
I thought Raj Bhaiya would break the record of his explanation, but he is still unbeatable.
Yes I can't agree more 😤😤🔥🔥
at 3:48 , deque should be Double ended queues I guess and not doubly linked list , btw nice explanation :)
I think he meant that double-ended queues are typically implemented using doubly linked lists
@@alokesh985 if i am not wrong in doubly linked list one can access,insert and pop elements at any position but in deque one can do it only at front and back
Good explanation. That's an art which is rare. Every one knows the steps and code and solution, But very few know the explanation and intution
14:22 ye time complexity O(n-k)+O(k) ni honi chahiye be because hum ans vector bhi to store kar rahe hai plz clear my doubt
Bro can u please make a video on how to deal with large numbers and what exactly 10^9+7.
Waiting for tree series eagerly.
Placement already started in college, and tree , dp, strings remaining from the sheet
A day before the interview at 2x speed.
Thanks man I was doubtful about the On complexity. your explanation cleared it :)
Thank You!!
bhaiya please bring more videos fast fast .. placements are starting!!
Understood Thanks Striver , I am suffering from health issues , Still not giving up.
Love❤😊
bhai tumhari video inti badiya hai to course laine ki jarurat hi nhi h
THank you bro.
Brute force+Optimized+code explanation---->complete video.
Thanks a ton.
we can also do this using simple sliding window technique !?
Wtf is this approach, sometimes you insert at the front, sometimes at the back, sometimes you pop, other times you say decreasing order then forget it, what the hell
We insert only at the back. That is the way it is done with it. We only remove it once in the front (when the limit of k exceeds) and once from back (when we encounter a greater element because we aren't forgetting the decreasing order)
Is the time complexity , really O(n) here ??.... because, if we take example, 6,4,5,3,2 with window size k =3, then once the greatest element 6 is removed, the next greatest element that is 5 should be placed at top, and for doing that worst case, there will be (k-1) comparisons. Anybody please correct me if I am wrong .
Time complexity for brute force sol is wrong
Ur explanation is so awesome.. It's really helpful to us..🙏
can you plzz upload the video of 862. Leeetcode problem Shortest Subarray with Sum at Least K.🙏🙏
please sir please I'm really stuck in this prblm.
The java code: ☕🌞
package subset;
import java.util.*;
public class maxSlidingWindow {
public static int[] maxSlide(int[] nums, int k) {
int[] ans=new int[nums.length-k+1];
int index=0;
Deque q=new LinkedList();
for(int i=0;i
How about using Max Heap with size K.. time complexity will be NLogN i guess.. Space complexity will be O(K)
Bhaiya Tree series kb ari h ek br date bta do pls...
100k pe. Ye me 100 wi baar bol raha 😵💫😂
The part that confuses me is dq.empty() or dq.front(), i thought they return a value at the index not the index itself. So how is it used here that it is checking the index and not the value? I am so confused.
Can someone explain why is this code giving me wrong answer after submitting on leetcode?
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vector ans;
int n = nums.size();
int i=0, j=0;
priority_queue q;
if(k > n){
ans.push_back(*max_element(nums.begin(), nums.end()));
}
while(j < n){
q.push(nums[j]);
if(j-i+1 < k) j++;
else if(j-i+1 >= k){
int top = q.top();
ans.push_back(top);
if(nums[i] == top) q.pop();
i++;
j++;
}
}
return ans;
}
};
New roast video out 🔥🔥
#BEINGFUNNYCASM
BEING FUNNYCASM yt channel
Bro please make a video on your jee journey
Thanks a lot! this was super helpful :)
we can't use equal to it will give wrong answer
Please add heap questions in SDE sheet.
can someone please explain me last if statement ??
3:20 - 6:25
I just had an interview with Google today and this was the algorithm I was given. That's why I'm here Haha. I was able to do it, but I took a different approach.
you can do by using a multiset as well , it takes nlogn but its very simple to write the code
great explanation bhai
Godly explanation. Suddenly, this problem does not look Leetcode Hard level
Worst case occurs when k = 1 , Inserting all N element and N-1 elements will be removed. This is because for each array element two operation DELETION -> INSERTION IS PERFORMED .
Great brother 👌👌 keep it up 👆
Ur explanation is so awesome.. It's really helpful to us..🙏
can you plzz upload the video of 862. Leeetcode problem Shortest Subarray with Sum at Least K.🙏🙏
please sir please I'm really stuck in this prblm.
Huge fan of your videos
here why we don't calculate the space complexity of the vector? Anyone?
why we should not directly give optimised solution of the particular problem in the interview
Bhaiya please make a video on the question: Find maximum of minimum for all the window sizes.
bro has unreal grudge on python
thanks for great explanation
can u explain last line r[ri++]=a[q.peek()];@19:29
not able to understand the lst part of the i>-=k-1 onwards part
I solved it using segment tree
how is the r[] size = int [n-k+1] can anyone explain?
Could not understand completely, but will come back
Nice explanation bro!
Thx a lot brother
thank you bhaiya
I understood the solution!
Can't find a better explanation than this for a hard problem.. simple love it
Understood sir
we can do this using queue also, why queue is not used and deque is used?
can we use max heap??
better than apna college
Thank You very much! You explain very well.
thank you striver!
Understood bhaiya ❤
easiest solution by naiveApproach
vector maxSlidingWindow(vector arr,int k){//TLE
vector ans;
int n= arr.size();
for (int i = 0; i < n-k+1; i++)
{
ans.push_back(*max_element(arr.begin()+i,arr.begin()+i+k)); // T.C = O(n) max_element
}
return ans;
}
understoooddddddd🥺❤
Ur explanation is so awesome.. It's really helpful to us..🙏
can you please upload the video of 862. Leetcode problem Shortest subarray with Sum at Least K.🙏🙏
please sir please I'm really stuck in this problem.
still i-k is confusing?
Question Link : leetcode.com/problems/sliding-window-maximum/