I forgot to address this edge condition: Note: If K > length of the array, return 1 element with the max of the array. Code for this would be: vector ans; if(k>v.size()) { ans.push_back(*max_element(v.begin(),v.end())); return ans; }
@Aditya Verma bhaiya as you mostly make videos on observing the patterns of questions and then solving them. Is it possible by you to prepare a sheet of questions which consist of various concepts and patterns and questions on them. bcoz making a lot of videos on them will take a lot of time. So if we get a list of such questions we can practice on our own. We will not use this list as a complete set but just to get familiar with the concept and pattern so that if any other new question comes we can atleast figure out the approach. It will be really very very helpful
the time you took separately to explain 1st incorrect approach is really appreciating. Initially maine wahi approach socha.. but later got to know ki it would not cover all cases. Thanks @Aditya...
Came here after watching 2 more videos. You're the only one who explained why the first approach was incorrect, others just directly jump to the solution. You're doing a wonderful job. Kudos man!
So i have been trying to understand this one question since a day. And trust me i have watched almost every single Indian RUclips explanation and i can say with utmost confidence that this is hands down the best explanation and now i have understood sliding window problem properly. Thanks bro .
Your First negetive number in every window helped in TCS NQT coding round....it was just cake walk problem because I watched it 1 day before exam😀😅... Thank you soo much Bhaiyaa
Explanation for why we need an ArrayDeque instead of a simple Queue: We have made use of an ArrayDeque in this question because we have made an assumption that we will always store the max element in FRONT of the queue. When we hit our window size, we just get the FRONT of the queue to get the max element for the window. If we would have not taken an ArrayDeque and used a normal Queue instead, in that case we would have violated the assumption that we made. For example assume we have I/P - arr:[6,4,5,4], k =3 O/P - [6,5] If we have taken ArrayDeque then our queue for the first window would look like - [6] i=0,j=0 [6,4] i=0,j=1 [6,5] i=0,j=2 which is correct because 6 > 5 and 5 > 4, so we remove 4 from the queue . But if we would have taken a normal Queue instead then we would have - [6] i=0,j=0 [6,4] i=0,j=1 [6,4,5] i=0,j=2 which is incorrect since 4 < 5 and it violates our assumption that max element will always be at the FRONT. then, for second window i=1,j=3 our queue would look like- [4,5,4] and we would get the O/P as [6,4] which is incorrect. Try it out!
I haven't even started learning sliding window....this question was in striver's A2Z sheet for stacks n queues.....I wasn't able to think of the approach....I saw striver's solution, he straightaway started telling the solution which was difficult to understand for me.....searched for the ques on youtube.....found aditya's video.....I kid you not I am justat 10:47 and I have already paused this video because I have got the intuition....I don't know if it is in the way he approaches the problem, I just see aditya's solution videos for a few minutes and I already have the solution in my mind.....GREAT WORK BROTHER
What the fuck bro how did you understand the problem at 10:47. The main problem of this question is to store the potential max elements in a data structure.which he explained after 20 minutes. How the fuck did you understand at starting 10 minutes bro.In every video he just waste the for 15 minutes by repeating again and agin same concept
For those who are getting wrong answers in some test cases: use deque instead of queue | C++ class Solution { public: vector max_of_subarrays(vector arr, int n, int k) { // your code here dequeq; int i=0,j=0; vectorres; while(j
@@divakarkumar1843 because deque is doubly linked list ... We can pop nd push from both side ... So for moving into the next window we have to pop the element from front and have to push the element from back.
@@Sh4h1dkh4nin the traditional queue too don't we push from the back and pop from the front? I'm quite stuck with what's wrong in this approach vector ans; int j=0; int i=0; queue q; if(nums.size()==1 || k==1) return nums; while(jq.front()) { q.pop(); } q.push(nums[j]); if(j-i+1q.front()) q.pop(); j++; i++; } } return ans;
You can also make use of secondMax within the window and when max is excluded from the window, make the secondMax the new max .Below is the snippet from c#. public static void MaximumInSubArrayOfGivenSize(int[] array, int subArraySize) { int start = 0, end = 0, max = int.MinValue, secondMax = int.MinValue; while(end < array.Length) { var windowSize = end - start + 1; if (array[end] > max) { max = array[end]; } if (array[end] > secondMax && array[end] < max) { secondMax = array[end]; } if(windowSize == subArraySize) { Console.Write(max + " "); if (array[start] == max) { max = secondMax; } start += 1; } end += 1; } }
Thanks! Great explanation as usual! @18:00 Your explanation of intuition behind using an two-ended DS is golden! That is what makes this video stand out from all other videos that simply say: use a monotonically decreasing queue.
@@tonyriddle7646 hey bro can you send the link of that tutorial i need to know all the approach in order to be really good at it so that i can diversify what i think.
If anyone interested in JS approach: const sliding = (arr, k) => { const l = [], res = [] let j = 0, i = 0 while(j < arr.length) { //remove all the elements which are less the elm at j while(l.length > 0 && l[l.length - 1] < arr[j]) l.pop() //push the curr max and elems after it...i.e. potential max elems l.push(arr[j]) if(j - i + 1 < k) j++ else if (j - i + 1 == k){ //push the max to res array (which is stored in front of list) res.push(l[0]) //check if max elm is getting lost when moving the window if(l[0] == arr[i]) l.shift() j++ i++ } } return res }
Gist of the logic:- 1. We have to create such a data structure which is open from both the sides, so that we can push and pop elements from any corner, and list is one such data structure. The first element of the list will contain maximum value of current window, the subsequent elements in the list are the candidate or possible maximum values for subsequent or future windows. 2. For jth value calculation- if the list is empty at first, then whatever comes first in the array will be pushed as maximum value in the list. In the list we need to store only those values which can become candidate maximum values for next sliding windows. So comparing jth value with the back of the list, if it comes out to be greater than the back of the list, then the back of the list becomes unused, as they can never become maximum value for future windows, so all these values which are less than the jth value needs to be deleted. If the jth value is less than the back of the list, it might not serve as the maximum value for the current window, but it can serve as the maximum value for future windows, so we need to preserve this, pushing them into the list for future use. 3. For retrieving the answer- the max value for the current window is always available at the front of the list, because all the values which are less than this value are deleted from the list, so the maximum value always occupies the first place in the list. 4. For sliding the window- before moving i and j iterators, we need to check whether the ith value belongs to the list or not. And it happens to belong to the list only if it has served as the maximum value for current window. If it hasn’t served as the max value, then there’s no chance that it can be found in the list. So deleting the front element of the list if it equals to ith value. Then i++ and j++.
Getting TLE in my solution: class Solution { public: vector maxSlidingWindow(vector& nums, int k) { int i=0,j=0; list tmp; vector ans; if(k==nums.size()){ ans.push_back(*max_element(nums.begin(),nums.end())); return ans; } while(j
Love you bro! Can't express your efforts Solution in python using list i=j=0 temp=[] result=[] n=len(arr) while j=arr[j] and temp[-1]>=arr[j]): temp.append(arr[j]) else: while temp!=[] and temp[-1]
vector max_of_subarrays(int *arr, int n, int k) { int i=0,j=0; list l; vector ans; while (j < n) { while(l.back()0){//calculation to remove smaller elements which are coming before j l.pop_back(); } l.push_back(arr[j]); if (j - i + 1 < k) { //moving pointer j to window size k j++; } else if (j - i + 1 == k) { ans.push_back(l.front());//as front element will be largest if(l.front()==arr[i]) l.pop_front();//removing 1st element before sliding window i++; //moving both pointers forward j++; } } return ans; }
instead of maintaining queue/list for storing useful elements, and then having logic, we can have maxHeap of windowSize and check peek, if its same as poping element pop from heap, easy ho jata to write and same in complexity as its logn for heapify anyway
You can't use heap because its not necessary that the element going out of the window is the largest in the heap, hence there wouldn't be an optimized way to remove it from the heap.
@@VipulGaur3 element going out need not be the largest. if we maintain a heap of size equal to window size, top() will always give max in that window, and as the window slides, keep popping the element at i, and adding element at j. Also, if you consider the complexity, heap addition/removal can be possible in O(log(k)) per element whereas if we choose to cleanup the list that takes up O(k) worst case.
use deque for solving this question and when inserting a new element in the deque. make sure to check from the back of the deque if the current element of the array is smaller than back of deque, then pop_back from deque until it gets empty or we find a greater element. Then only the code will work. Took me several hours to figure it out.
No since we will not be always removing the element at the ith index while moving the window. We will remove it only remove it if the element at the ith index is the max element i.e. top element. So will create problems in some cases. I submitted it in leetcode and it passed 40/51 cases. Here's what I did which is wrong vector maxSlidingWindow(vector& nums, int k) { int n = nums.size(); int i = 0; int j = 0; vector ans;
Bhai bhai Respect infinity for you bro . The way you explain it's impossible for someone to not understand it . We are bound to understand . Op brother keep the good work up. Love you bro.
I would say the 'next greater element' problem (from monotonic stack) is a per-requisite for this, as the exact concept is used here. If you have solved that problem, this one should be a cake walk.
if someone is struggling with the code this can be helpful as it is written according to what explained in video vector maxSlidingWindow(vector& nums, int k) {
Excellent explanation. But, Fails for [1,3,1,2,0,5] and k=3. For third window [1,2,0], ans is 2 but as per mentioned algo we get 1 We can use priority queue
without using list : void max_subArray(int arr[], int n, vector &MA, int k) { int i = 0, j = 0; int mx = INT_MIN; if (k > n){ MA.push_back(*max_element(arr, arr + n)); return; } while (j < n) { if (j - i + 1 < k) { mx = max(mx, arr[j]); j++; } else if (j - i + 1 == k) { // MA.push_back(*max_element(arr + i , arr + j + 1)); mx = max(mx, arr[j]); MA.push_back(mx); // this condition is used when first value in the array is max element if (mx == arr[i] ) mx = max(arr[i + 1], arr[i + 2]); // slide the window i++; j++; } } }
@@BhatiJhabarSingh Nope even for worst case descending order this would be O(2*N) = O(N). Every element gets added ONCE and deleted ONCE from the queue.
Even I am thinking the same..if we will store everything in a max heap then if the first element (element at i) of the window is popped and if that element is the maximum element then for the remaining portion of window we can extract the top of max heap
excellent, but i thinjk you made one tiny mistake. in the condition where Window size hits k, it should be a else if. this is because we only want one of the conditions (WS < k OR WS ==k) to run in one iteration of the loop. instead of elseif(WS==k), you could also just put a continue after j+=1
bhai, sorry to say but you have elongated the video by at least 20 mins just by repeating content again and again...not once or twice but 6-7 times...in RUclips one can easily pause and repeat...conceptually the video is good, but elongated without purpose
For those who wanted to get the answer in Java class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int[] ans = new int[nums.length-k+1]; int i=0,j=0; Deque deque = new LinkedList(); while(j0 && deque.peekLast()
#include vector Solution::slidingMaximum(const vector &arr, int k) { vectorans; // edge case when k greater than our array size if(k > arr.size()) { ans.push_back(*max_element(arr.begin(),arr.end())); return ans; } int i=0, j=0;
listl; int n = arr.size(); while(j < n) { // doing calculations // in window size jo element mere particular element se small hai or mujhe nhi chahiye. while(l.size()>0 && l.back() < arr[j]) { l.pop_back(); } // after than i add into list. l.push_back(arr[j]);
if(j-i+1 < k) { j++; }
else if(j-i+1==k) { // derive answer from calculations ans.push_back(l.front());
// if first element is my maximum element if(arr[i]==l.front()) { l.pop_front(); } i++,j++; } }
exactly How to be sure that after pooping max we get the next min of (k-1) window.. for ex if arr was [3,-3,1,...]...our list would have been[3,-3,-1] but in this case (l.front()==max) then when we pop 3 our list becomes [-3,-1] but here -3 is not max..-1 is..so what to do here? one thing we can do is if l.size() > 1 then if v[0]
Yes same doubt!!! can this be solved only using a simple queue(linkedlist implementation)? not priority queue or dequeue in java? arr=[5,2,3,1] k=3 first window 5 2 3, in queue we store 5 2 3, so here max is 5. next window 2 3 6, removed 5, now new top is 2, which wil be returned as max, but we need to return 2. How to handle this using only queue? is it possible? with the same logic as explained in the video? pls reply anyone
Wouldn't it be easier to use priority-queue instead of list. Priority-queue will by default sort as per max element in the container and hence there is no need to compare & pop elements.
yes we can here is the code for it - static ArrayList max_of_subarrays(int arr[], int n, int k) { // Your code here ArrayList array = new ArrayList(); int i = 0; int j = 0; PriorityQueue queue = new PriorityQueue(Collections.reverseOrder()); while(j k) { queue.remove(arr[i]); i++; } if (j - i + 1 == k) { array.add(queue.peek()); } j++; } return array; }
yes we can use priority_queue but this sweet brings it's own poison. I have written a self removeEle function for this to work, this will run whenever we know that element which is out going out of bound of subarray, must be removed from priority_queue as well and this adds us the time complexity to (N*totalNo. of eles in PQ) at worst case and hence this solution will give TLE for higher valued input. Hope this helps void removeEle(int target, priority_queue &pq){
vector temp; while(!pq.empty()){ int top = pq.top(); pq.pop(); if(top == target){ break; } temp.push_back(top); } for(int it : temp){ pq.push(it); } } vector maxSlidingWindow(vector& nums, int k) { int i = 0; int j = 0; vector ans; priority_queue pq; int n = nums.size(); while(j < n){ // global calc pq.push(nums[j]); if(j-i+1 < k) j++; else if(j-i+1 == k){ // local cal -> for potential answer ans.push_back(pq.top());
// slide the window -> removal part if(nums[i] == pq.top()) pq.pop(); else { // this is where this self defined function will be used to remove particular element from PQ removeEle(nums[i],pq); } // maintain sliding window size i++; j++; } } return ans; } and i am using c++ before any Java coder finds this funny :)
A Simple and Easy to understand Python Code: class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: i,j=0,0 arr = deque([]) vector=[] while j
Total Time Taken: 4.67 gfg all test cases passed its a bit different and comparitively not the best solution but i hope it helps :) class Solution { //Function to find maximum of each subarray of size k. static ArrayList max_of_subarrays(int arr[], int n, int k) { // Your code hereA ArrayList list=new ArrayList(); int i=0,j=0; int max=Integer.MIN_VALUE; int ans=Integer.MIN_VALUE; while(j
using python as the language. Can do it with two lists as well right ? arr = [3, 2, 1, 5] i = j = 0 k = 3 dump = [] max_arr = [] while j < len(arr): dump.append(arr[j]) if(j - i + 1 < k): j += 1 elif(j - i + 1 == k): max_arr.append(max(dump)) dump.pop(0) i += 1 j += 1 print(max_arr)
take an example of strictly decreasing arr,here the leaving term is maximum, so you will search the window once again for maximum value, on every consecutive window size, you have to iterate through the whole window, ultimately one element will be traversed for k times (window size). Hence this approach is wrong @Aditya Verma
LOGIC + CODE LOGIC-> watch carefully //|Actual logic | //(comment mentioned in code) we will keep only larger elements in the because lets say if we iterate a k size window (only one element is present which larger than upcomming elements ) if we counter smaller element first and then larger element we need to pop the smaller element bcoz those elements are no need to us Hence, logic satisfies vector maxSlidingWindow(vector& nums, int k) { int n = nums.size(); vector ans; deque dq; int i=0, j=0; while (j
Code in C++ class Solution { public: //Function to find maximum of each subarray of size k. vector max_of_subarrays(int *arr, int n, int k) { // your code here vector ans; list l; int i=0,j=0; while(j 0 && l.back()
Indirectly this means in the sliding window maximum problem, at any instant of time, our list will contain elements in decreasing order (largest at the front() and smallest at the back ()).
absolutely great video....your approach is great in every problem you solve....but i think in this que.....when you were explaining that after finding a max element in window size...the elements after it are useful as they can be maximum in some other window (@ 25:05)....i think you miss one case there.....the point is not every single element after we found maximum in first window of size k are important...its not like that....the thing is that we have to keep the next maximum after we found the first maximum in queue....(through checking when we are inserting element in queue...check if teh element is greater than the last element of queue ...if it is so..then remove last element and insert the current eleement)....in this way when we remove the ith element when we slide window we will automatically get the max element before doing j++........in this case k was small so this case didnt arise....also after removing 3 from this case....when u inserted -3 in the queue, you got -1 as next max oly because -1 is already > than -3....what if 0 was there instead of -3.....then the queue would have looked like [-1,0]....which gives -1 as max ele for next window (before j++) which is wrong.....
if array is 3 -1 0 then while inserting 0, -1 will already be removed from queue. because at any point during insertion all elements less then the currently inserted element are already removed
I forgot to address this edge condition:
Note: If K > length of the array, return 1 element with the max of the array.
Code for this would be:
vector ans;
if(k>v.size())
{
ans.push_back(*max_element(v.begin(),v.end()));
return ans;
}
@Aditya Verma bhaiya as you mostly make videos on observing the patterns of questions and then solving them. Is it possible by you to prepare a sheet of questions which consist of various concepts and patterns and questions on them. bcoz making a lot of videos on them will take a lot of time. So if we get a list of such questions we can practice on our own. We will not use this list as a complete set but just to get familiar with the concept and pattern so that if any other new question comes we can atleast figure out the approach. It will be really very very helpful
should be ans.push_back(*max_element(v.begin(),v.end())+1);
@@ankita1464 Agreed!
What if we use min heap instead of list
@@mohsinabbassayyed9610 not min heap but max heap
the time you took separately to explain 1st incorrect approach is really appreciating. Initially maine wahi approach socha.. but later got to know ki it would not cover all cases. Thanks @Aditya...
Came here after watching 2 more videos. You're the only one who explained why the first approach was incorrect, others just directly jump to the solution. You're doing a wonderful job. Kudos man!
Actually 2nd approach is also wrong, but this comment is 2 year old so my comment has no impact
😂😂@@princenagar1686
@@princenagar1686 Can you elaborate why the 2nd approach will be wrong.
So i have been trying to understand this one question since a day. And trust me i have watched almost every single Indian RUclips explanation and i can say with utmost confidence that this is hands down the best explanation and now i have understood sliding window problem properly.
Thanks bro .
Your First negetive number in every window helped in TCS NQT coding round....it was just cake walk problem because I watched it 1 day before exam😀😅... Thank you soo much Bhaiyaa
Glad it helped ✌️ Keep watching ✅
please add more videos bhaiya, from last 6-7 month i haven't seen any update in the course please.
do that level questions asked in tcs interview😵
@@GULLAPUDILIKITHBCE that is a easy question.
@@madhabkafle8898 ha ya after understanding now it seems easy to me:)
Explanation for why we need an ArrayDeque instead of a simple Queue:
We have made use of an ArrayDeque in this question because we have made an assumption that we will always store the max element in FRONT of the queue. When we hit our window size, we just get the FRONT of the queue to get the max element for the window.
If we would have not taken an ArrayDeque and used a normal Queue instead, in that case we would have violated the assumption that we made. For example assume we have
I/P - arr:[6,4,5,4], k =3
O/P - [6,5]
If we have taken ArrayDeque then our queue for the first window would look like -
[6] i=0,j=0
[6,4] i=0,j=1
[6,5] i=0,j=2
which is correct because 6 > 5 and 5 > 4, so we remove 4 from the queue .
But if we would have taken a normal Queue instead then we would have -
[6] i=0,j=0
[6,4] i=0,j=1
[6,4,5] i=0,j=2
which is incorrect since 4 < 5 and it violates our assumption that max element will always be at the FRONT.
then, for second window i=1,j=3 our queue would look like-
[4,5,4] and we would get the O/P as [6,4] which is incorrect.
Try it out!
Thanks mate!
Thanks man! Helped me visualize solution
Actually we can't push_back in case of queue . Is this the reason
bro you are a genius
thanks a lot
Love the way you explain every point, again and again; when I get confused at some point, you always explain that thing again :)
I haven't even started learning sliding window....this question was in striver's A2Z sheet for stacks n queues.....I wasn't able to think of the approach....I saw striver's solution, he straightaway started telling the solution which was difficult to understand for me.....searched for the ques on youtube.....found aditya's video.....I kid you not I am justat 10:47 and I have already paused this video because I have got the intuition....I don't know if it is in the way he approaches the problem, I just see aditya's solution videos for a few minutes and I already have the solution in my mind.....GREAT WORK BROTHER
What the fuck bro how did you understand the problem at 10:47. The main problem of this question is to store the potential max elements in a data structure.which he explained after 20 minutes. How the fuck did you understand at starting 10 minutes bro.In every video he just waste the for 15 minutes by repeating again and agin same concept
So don't be just dumb and praise him for unnecessary reasons
For those who are getting wrong answers in some test cases: use deque instead of queue | C++
class Solution {
public:
vector max_of_subarrays(vector arr, int n, int k) {
// your code here
dequeq;
int i=0,j=0;
vectorres;
while(j
why ??
Thanks amazing solution
@@divakarkumar1843 because deque is doubly linked list ... We can pop nd push from both side ... So for moving into the next window we have to pop the element from front and have to push the element from back.
thanks bro:)
@@Sh4h1dkh4nin the traditional queue too don't we push from the back and pop from the front?
I'm quite stuck with what's wrong in this approach
vector ans;
int j=0;
int i=0;
queue q;
if(nums.size()==1 || k==1) return nums;
while(jq.front()) {
q.pop();
}
q.push(nums[j]);
if(j-i+1q.front()) q.pop();
j++;
i++;
}
}
return ans;
You can also make use of secondMax within the window and when max is excluded from the window, make the secondMax the new max .Below is the snippet from c#.
public static void MaximumInSubArrayOfGivenSize(int[] array, int subArraySize)
{
int start = 0, end = 0, max = int.MinValue, secondMax = int.MinValue;
while(end < array.Length)
{
var windowSize = end - start + 1;
if (array[end] > max)
{
max = array[end];
}
if (array[end] > secondMax && array[end] < max)
{
secondMax = array[end];
}
if(windowSize == subArraySize)
{
Console.Write(max + " ");
if (array[start] == max)
{
max = secondMax;
}
start += 1;
}
end += 1;
}
}
Thanks! Great explanation as usual! @18:00 Your explanation of intuition behind using an two-ended DS is golden! That is what makes this video stand out from all other videos that simply say: use a monotonically decreasing queue.
could you provide the code for the same
@@tonyriddle7646 hey bro can you send the link of that tutorial i need to know all the approach in order to be really good at it so that i can diversify what i think.
If anyone interested in JS approach:
const sliding = (arr, k) => {
const l = [], res = []
let j = 0, i = 0
while(j < arr.length) {
//remove all the elements which are less the elm at j
while(l.length > 0 && l[l.length - 1] < arr[j])
l.pop()
//push the curr max and elems after it...i.e. potential max elems
l.push(arr[j])
if(j - i + 1 < k)
j++
else if (j - i + 1 == k){
//push the max to res array (which is stored in front of list)
res.push(l[0])
//check if max elm is getting lost when moving the window
if(l[0] == arr[i])
l.shift()
j++
i++
}
}
return res
}
@
@akhileshshahare Thanks for sharing. 👍
i was stuck on this problem for quite some time. thank you
Please make a series on graphs, it would help a lot.
Thanks for the previous videos...
Gist of the logic:-
1. We have to create such a data structure which is open from both the sides, so that we can push and pop elements from any corner, and list is one such data structure. The first element of the list will contain maximum value of current window, the subsequent elements in the list are the candidate or possible maximum values for subsequent or future windows.
2. For jth value calculation- if the list is empty at first, then whatever comes first in the array will be pushed as maximum value in the list. In the list we need to store only those values which can become candidate maximum values for next sliding windows. So comparing jth value with the back of the list, if it comes out to be greater than the back of the list, then the back of the list becomes unused, as they can never become maximum value for future windows, so all these values which are less than the jth value needs to be deleted. If the jth value is less than the back of the list, it might not serve as the maximum value for the current window, but it can serve as the maximum value for future windows, so we need to preserve this, pushing them into the list for future use.
3. For retrieving the answer- the max value for the current window is always available at the front of the list, because all the values which are less than this value are deleted from the list, so the maximum value always occupies the first place in the list.
4. For sliding the window- before moving i and j iterators, we need to check whether the ith value belongs to the list or not. And it happens to belong to the list only if it has served as the maximum value for current window. If it hasn’t served as the max value, then there’s no chance that it can be found in the list. So deleting the front element of the list if it equals to ith value. Then i++ and j++.
Thanks for explanation
Thank you very much ..as I don't know Hindi.. Your explanation is very useful
@@snegar1677 Glad! It helped You🙃
@enigmans07Glad! It helped you😊
Thank you
Goddess of Clarity Universe.
your channel deserves to be hyped !!! tysm(happy tears)
LEETCODE:
class Solution {
public:
vector maxSlidingWindow(vector& array, int k) {
list list;
vector ans;
int i =0, j=0;
while(j0 && list.back()
LeetCode
239. Sliding Window Maximum
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
max_vals = []
ans = []
i = j = 0
n = len(nums)
while(j
LeetCode 239:
vector maxSlidingWindow(vector& nums, int k) {
listli;
vectorans;
int i=0,j=0;
while(j0 && li.back()
Bhaiya ko bhi btana chiye tha leetcode pr konsa q h... But koi ni thanks for sharing
Getting TLE in my solution:
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int i=0,j=0;
list tmp;
vector ans;
if(k==nums.size()){
ans.push_back(*max_element(nums.begin(),nums.end()));
return ans;
}
while(j
Thanks
Great explanation :)
Quick side note we need to use either a list or a deque and not a queue in this question.
why he has only 2.3 lakh subscribers, mannnn he deserved more. please do subscribe guys
One of the best explanation ever for this video
thanku bhaiya...... after watching it mre than 5 times i got the intuition
Love you bro! Can't express your efforts
Solution in python using list
i=j=0
temp=[]
result=[]
n=len(arr)
while j=arr[j] and temp[-1]>=arr[j]):
temp.append(arr[j])
else:
while temp!=[] and temp[-1]
we can also use a max heap as the data structure but the complexity will increase to nlogn
*Java - LeetCode 239 solution*
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int ans[] = new int[nums.length - k + 1];
Deque q = new LinkedList();
int i = 0;
int j = 0;
while(j < nums.length){
// calculation
if(q.size() == 0){
q.add(nums[j]);
}
else{
while(q.size() > 0 && q.peekLast() < nums[j]){
q.removeLast();
}
q.add(nums[j]);
}
// now move j pointer
if(j - i + 1 < k) j++;
// if we hit the window size
else if(j - i + 1 == k){
// answer -> calculation;
ans[i] = q.peek();
// slide the window
// calculation
if(nums[i] == q.peek()){
q.removeFirst();
}
// now slide the pointer
i++;
j++;
}
}
return ans;
}
}
Thank you
Tu striver ka video dekh ke Aya hai😂
Thank u bro
@@amitmahato6404 😂
Missing the pen rotation again😅
vector max_of_subarrays(int *arr, int n, int k)
{
int i=0,j=0;
list l;
vector ans;
while (j < n)
{
while(l.back()0){//calculation to remove smaller elements which are coming before j
l.pop_back();
}
l.push_back(arr[j]);
if (j - i + 1 < k)
{ //moving pointer j to window size k
j++;
}
else if (j - i + 1 == k)
{
ans.push_back(l.front());//as front element will be largest
if(l.front()==arr[i]) l.pop_front();//removing 1st element before sliding window
i++; //moving both pointers forward
j++;
}
}
return ans;
}
If u have seen previous all vdo then u can start from 9:00
Thank you bro
class Solution:
def solve(self,arr,k):
i,j,=0,0
mx=0
ans=[]
while j
20:57…one line that addressed my whole doubt..ye 1 kaam ayega ki nahi👌🏻
instead of maintaining queue/list for storing useful elements, and then having logic, we can have maxHeap of windowSize and check peek, if its same as poping element pop from heap, easy ho jata to write and same in complexity as its logn for heapify anyway
You can't use heap because its not necessary that the element going out of the window is the largest in the heap, hence there wouldn't be an optimized way to remove it from the heap.
@@VipulGaur3 element going out need not be the largest. if we maintain a heap of size equal to window size, top() will always give max in that window, and as the window slides, keep popping the element at i, and adding element at j. Also, if you consider the complexity, heap addition/removal can be possible in O(log(k)) per element whereas if we choose to cleanup the list that takes up O(k) worst case.
int i=0,j=0;
vector ans;
int n=A.size();
if(B>n){
return ans;
}
else if(B==n){
ans.push_back(*max_element(A.begin(),A.end()));
return ans;
}
multiset s;
while(j
use deque for solving this question and when inserting a new element in the deque. make sure to check from the back of the deque if the current element of the array is smaller than back of deque, then pop_back from deque until it gets empty or we find a greater element. Then only the code will work. Took me several hours to figure it out.
searching someone notice this error or not , finally find your comment.
thank you for the confirmation brother.
i got stuck at the same place
thanks brother
Can we use heap data structure to procure the maximum element for each window ?
No since we will not be always removing the element at the ith index while moving the window. We will remove it only remove it if the element at the ith index is the max element i.e. top element. So will create problems in some cases. I submitted it in leetcode and it passed 40/51 cases. Here's what I did which is wrong
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
int i = 0;
int j = 0;
vector ans;
priority_queue pq; //max heap
while(j < n)
{
pq.push(nums[j]);
if(j-i+1 < k)
j++;
else if(j-i+1 == k)
{
ans.push_back(pq.top());
if(nums[i] == pq.top())
pq.pop();
i++;
j++;
}
}
return ans;
}
We can correct this by always removing the ith element from the heap but it will be lengthy
badhiya bata diye aap.... sahi.... O(nlogn) tow soch liye they..lekin ye O(n) mein accha solution tha
This is the best explaination period!
can priority queue(max heap) be used?
bhaiya graph bi start kr do....we r waiting for it..
@TheAdityaVerma
at 05:00, brute force takes time O(nk) and not O(n^2)
in worst vcase window size can be upto the size of array thats why n^2
Bhai bhai Respect infinity for you bro . The way you explain it's impossible for someone to not understand it . We are bound to understand . Op brother keep the good work up. Love you bro.
Using Prioirty-Queue :
vector maxSlidingWindow(vector& nums, int k) {
vector ans;
priority_queue heap;
for(int i = 0; i < k; i++){
heap.push({nums[i], i});
}
ans.push_back(heap.top().first);
for(int i = k; i < nums.size(); i++){
heap.push({nums[i], i});
while(heap.top().second
Explained Approach handling edge case can be implemented as:-
vector maxSlidingWindow(vector& A, int B) {
vector ans;
if(A.size()
Thank you so much aditya. your videos are helping me a lot in preparation. your explanations are much better than so many others on you tube.
we can use deque for O(n) complexity
This question will become very easy when we use multiset (in c++ STL) instead of list of queue.
Thankyou so much aditya verma sir🐰🐰🐰🔥.. Dammm this is too good problem
your videos are awesome, just help me a lot in improving my thinking skills. Thanks a lot for this amazing series.
I would say the 'next greater element' problem (from monotonic stack) is a per-requisite for this, as the exact concept is used here. If you have solved that problem, this one should be a cake walk.
if someone is struggling with the code this can be helpful as it is written according to what explained in video
vector maxSlidingWindow(vector& nums, int k) {
vector output;
int i=0;
int j=0;
list l;
while(j
if(l.empty()){
l.push_back(nums[j]);
}
else
{
while(!l.empty() && l.back()
@@aakritisingh399 Yes True
@@aakritisingh399 Why did we take List we could have done the same thing in vector right?
hu
@@adityagandhi3003 if vector jas push_back and pop, you can use it too. In python, we use List
Excellent explanation.
But, Fails for [1,3,1,2,0,5] and k=3. For third window [1,2,0], ans is 2 but as per mentioned algo we get 1
We can use priority queue
no , the algorithm is correct and answer is [3,3,2,5]
Exactly same I stuck her4
1 bda h 0 s to usko popnahi kiya jayega then 1 to bda nahi h is window m
Use this
while( !l.empty() && l.back()< nums[j] ){
l.pop_back();
}
without using list :
void max_subArray(int arr[], int n, vector &MA, int k) {
int i = 0, j = 0;
int mx = INT_MIN;
if (k > n){
MA.push_back(*max_element(arr, arr + n));
return;
}
while (j < n) {
if (j - i + 1 < k) {
mx = max(mx, arr[j]);
j++;
}
else if (j - i + 1 == k) {
// MA.push_back(*max_element(arr + i , arr + j + 1));
mx = max(mx, arr[j]);
MA.push_back(mx);
// this condition is used when first value in the array is max element
if (mx == arr[i] ) mx = max(arr[i + 1], arr[i + 2]);
// slide the window
i++;
j++;
}
}
}
Time complexity..?
solution using multiset
vector max_of_subarrays(int *arr, int n, int k)
{
int i=0,j=0;
multisets;
vectorv;
while(j
Thanks Aditya. Your videos are awesome.
Additionally, Complexity would be O(N*K). We can use max heap here to reduce complexity to O(NlogK).
O(n) for the approach in video
@@thePankajsingh90 no bro it's O(n*k) take reverse sorted array
@harsh bro how did you calculated compelxity for max heap .
@@BhatiJhabarSingh Nope even for worst case descending order this would be O(2*N) = O(N). Every element gets added ONCE and deleted ONCE from the queue.
bhai i am trying max heap..not working time limit exceeded with 49/61 test case passd...if u still have the code ..please share
multi set solution:
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k)
{
multiset set;
int i=0,j=0;
int n = nums.size();
vectorans;
while(j
Great Explanation :)
Sep'26, 2023 05:40 pm
Bro ,why this time and date?🫡
@@anmolverma075 To check how much I have done since then..
Great explanation but it really frustrates when you keep explaining what the question is again and again. Arey bhai ek baar me samjh aa gaya!
very nice explain
Can there be any case where storing elements in the deque will fail? Instead we can store indices.
Can we use max heap for getting the maximum of the window.
I guess
I THINK WE SHOULD USE SET RATHER BECAUSE DELETION WOULD BE COSTLIER IN HEAP.
Even I am thinking the same..if we will store everything in a max heap then if the first element (element at i) of the window is popped and if that element is the maximum element then for the remaining portion of window we can extract the top of max heap
Using maxheap will change complexity from O(n) to O(nlogn)
@@kirtikedia6274 O(N*log K)
excellent, but i thinjk you made one tiny mistake.
in the condition where Window size hits k, it should be a else if.
this is because we only want one of the conditions (WS < k OR WS ==k) to run in one iteration of the loop.
instead of elseif(WS==k), you could also just put a continue after j+=1
Yes
little confused why we are getting the wrong answer using queue and why to use deque?
because in queue push can be done from 1 side and pop from another side but in enqueue you can do push and pop from any side
multiset st;
for(int i = 0; i < k; i++)
{
st.insert(arr[i]);
}
vector ans;
ans.push_back(*st.begin());
for(int i = 1; i
bhai, sorry to say but you have elongated the video by at least 20 mins just by repeating content again and again...not once or twice but 6-7 times...in RUclips one can easily pause and repeat...conceptually the video is good, but elongated without purpose
I think use of Max Heap as the data structure will be simpler than maintaining the list.
For those who wanted to get the answer in Java
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] ans = new int[nums.length-k+1];
int i=0,j=0;
Deque deque = new LinkedList();
while(j0 && deque.peekLast()
#include
vector Solution::slidingMaximum(const vector &arr, int k) {
vectorans;
// edge case when k greater than our array size
if(k > arr.size())
{
ans.push_back(*max_element(arr.begin(),arr.end()));
return ans;
}
int i=0, j=0;
listl;
int n = arr.size();
while(j < n)
{
// doing calculations
// in window size jo element mere particular element se small hai or mujhe nhi chahiye.
while(l.size()>0 && l.back() < arr[j])
{
l.pop_back();
}
// after than i add into list.
l.push_back(arr[j]);
if(j-i+1 < k)
{
j++;
}
else if(j-i+1==k)
{
// derive answer from calculations
ans.push_back(l.front());
// if first element is my maximum element
if(arr[i]==l.front())
{
l.pop_front();
}
i++,j++;
}
}
return ans;
}
//simple and straight forward
explains same thing repetitively , loosing intererst to listen, but your efforts are appreciated to explain in layman terms
bhut bhadiya explaination sir
Only 10 mins into the video and i can solve it comfortably. That's how good a teacher your are
Didn't understand why even after poping the maximum and front element in the queue we can still get the new maximum element in the new front..
exactly How to be sure that after pooping max we get the next min of (k-1) window.. for ex if arr was [3,-3,1,...]...our list would have been[3,-3,-1] but in this case (l.front()==max) then when we pop 3 our list becomes [-3,-1] but here -3 is not max..-1 is..so what to do here? one thing we can do is if l.size() > 1 then if v[0]
@@bhaskararya9112 ya same doubt suppose if the first three elements are 3 1 2
we can solve that problem by using priority queue
@@NitinSharma-bk7dw How to handle this case only using a normal queue(linkedlist implementation) not dequeue or priority queue?
Yes same doubt!!!
can this be solved only using a simple queue(linkedlist implementation)? not priority queue or dequeue in java?
arr=[5,2,3,1] k=3 first window 5 2 3, in queue we store 5 2 3, so here max is 5.
next window 2 3 6, removed 5, now new top is 2, which wil be returned as max, but we need to return 2. How to handle this using only queue? is it possible? with the same logic as explained in the video? pls reply anyone
We are using deque , removing first element of redundant index and adding element at last
Thank you very much. You are a genius.
Wouldn't it be easier to use priority-queue instead of list. Priority-queue will by default sort as per max element in the container and hence there is no need to compare & pop elements.
yes we can here is the code for it -
static ArrayList max_of_subarrays(int arr[], int n, int k)
{
// Your code here
ArrayList array = new ArrayList();
int i = 0;
int j = 0;
PriorityQueue queue = new PriorityQueue(Collections.reverseOrder());
while(j k) {
queue.remove(arr[i]);
i++;
}
if (j - i + 1 == k) {
array.add(queue.peek());
}
j++;
}
return array;
}
yes we can use priority_queue but this sweet brings it's own poison.
I have written a self removeEle function for this to work, this will run whenever we know that element which is out going out of bound of subarray, must be removed from priority_queue as well and this adds us the time complexity to (N*totalNo. of eles in PQ) at worst case and hence this solution will give TLE for higher valued input. Hope this helps
void removeEle(int target, priority_queue &pq){
vector temp;
while(!pq.empty()){
int top = pq.top();
pq.pop();
if(top == target){
break;
}
temp.push_back(top);
}
for(int it : temp){
pq.push(it);
}
}
vector maxSlidingWindow(vector& nums, int k) {
int i = 0;
int j = 0;
vector ans;
priority_queue pq;
int n = nums.size();
while(j < n){
// global calc
pq.push(nums[j]);
if(j-i+1 < k) j++;
else if(j-i+1 == k){
// local cal -> for potential answer
ans.push_back(pq.top());
// slide the window -> removal part
if(nums[i] == pq.top()) pq.pop();
else {
// this is where this self defined function will be used to remove particular element from PQ
removeEle(nums[i],pq);
}
// maintain sliding window size
i++;
j++;
}
}
return ans;
}
and i am using c++ before any Java coder finds this funny :)
@@tanmayajain7761why are we using max variable here? What is it's purpose here?
@@hajeeramohamad7641 no use, It's commented.
A Simple and Easy to understand Python Code:
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
i,j=0,0
arr = deque([])
vector=[]
while j
just a doubt, if we are having nested while loop ( one while for array traversal and one inside calculation), won't it generally make it o(n2)?
Total Time Taken:
4.67
gfg all test cases passed
its a bit different
and comparitively not the best solution
but i hope it helps :)
class Solution
{
//Function to find maximum of each subarray of size k.
static ArrayList max_of_subarrays(int arr[], int n, int k)
{
// Your code hereA
ArrayList list=new ArrayList();
int i=0,j=0;
int max=Integer.MIN_VALUE;
int ans=Integer.MIN_VALUE;
while(j
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
// sliding window ques
vector ans;
int i=0,j=0;
list maxVal;
while(j
Can't we use Priority Queue with max heap to avoid this manual work of maintaining queue?
please Aditya sir make video on graph ,trees, backtracking we are waiting for upcoming lectures on mentioned topic above
best explanation so far!
Can we use maxheap instead of Deque????
using python as the language. Can do it with two lists as well right ?
arr = [3, 2, 1, 5]
i = j = 0
k = 3
dump = []
max_arr = []
while j < len(arr):
dump.append(arr[j])
if(j - i + 1 < k):
j += 1
elif(j - i + 1 == k):
max_arr.append(max(dump))
dump.pop(0)
i += 1
j += 1
print(max_arr)
take an example of strictly decreasing arr,here the leaving term is maximum, so you will search the window once again for maximum value, on every consecutive window size, you have to iterate through the whole window, ultimately one element will be traversed for k times (window size). Hence this approach is wrong @Aditya Verma
What is time complexity of this approach?
Since he is using while loop delete ele...is it still O(n)?
LOGIC + CODE
LOGIC->
watch carefully //|Actual logic | //(comment mentioned in code)
we will keep only larger elements in the because
lets say if we iterate a k size window (only one element is present which larger than upcomming elements )
if we counter smaller element first
and then larger element
we need to pop the smaller element bcoz those elements are no need to us
Hence,
logic satisfies
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
vector ans;
deque dq;
int i=0, j=0;
while (j
vector max_of_subarrays(int *arr, int n, int k)
{
// your code here
int left=0, right=0;
list l;
vector result;
while(right 0 && l.back()
i am doing same code using queue but i m not getting answer can u tell me the diff b/w list and queue
Couldn't we use some sort of max heap to store the elements of window size k and then return top of it always...and do calculations accordingly?
why we have put up the while condition,I m not able to understand ...while(j
yes, as j can go upto max size of array-1
Code in C++
class Solution
{
public:
//Function to find maximum of each subarray of size k.
vector max_of_subarrays(int *arr, int n, int k)
{
// your code here
vector ans;
list l;
int i=0,j=0;
while(j 0 && l.back()
vector maxSlidingWindow(vector& nums, int k)
{
int arr_size = nums.size();
dequedq;
vectorans;
int Start=0, End=0;
while(End < arr_size)
{
// Processing - Part 1
while(!dq.empty() && nums[End]> dq.back())
dq.pop_back();
dq.push_back(nums[End]);
int window = End-Start+1;
if(window==k)
{
// Getting Answer - Part 2
ans.push_back(dq.front());
// Sliding Portion - Part 3
if(nums[Start] == dq.front())
dq.pop_front();
Start++;
}
End++;
}
return ans;
}
instead of list,wouldnt it better to use maxheap data structure?
if we use maxheap then the tc will be O(n*log k) and if we use list tc will be O(n)
Explained this so well!! Thank you bhai!
javascript solution :-
let string = [1,2,3,-1,-5,-9,2,8,9]
function solve(array1,k) {
let i = 0
let j = 0;
let array = []
let max = []
while(j < string.length){
while (max.length > 0 && max[max.length-1] < array1[j]) {
max.pop()
}
max.push(array1[j])
if(j - i + 1 < k ){
j++
}else{
array.push(max[0])
if(array1[i] == max[0]){
max.shift()
}
i++
j++
}
}
return array
}
console.log(solve(string,3))
Indirectly this means in the sliding window maximum problem, at any instant of time, our list will contain elements in decreasing order (largest at the front() and smallest at the back ()).
yes exactly
absolutely great video....your approach is great in every problem you solve....but i think in this que.....when you were explaining that after finding a max element in window size...the elements after it are useful as they can be maximum in some other window (@ 25:05)....i think you miss one case there.....the point is not every single element after we found maximum in first window of size k are important...its not like that....the thing is that we have to keep the next maximum after we found the first maximum in queue....(through checking when we are inserting element in queue...check if teh element is greater than the last element of queue ...if it is so..then remove last element and insert the current eleement)....in this way when we remove the ith element when we slide window we will automatically get the max element before doing j++........in this case k was small so this case didnt arise....also after removing 3 from this case....when u inserted -3 in the queue, you got -1 as next max oly because -1 is already > than -3....what if 0 was there instead of -3.....then the queue would have looked like [-1,0]....which gives -1 as max ele for next window (before j++) which is wrong.....
if array is 3 -1 0 then while inserting 0, -1 will already be removed from queue. because at any point during insertion all elements less then the currently inserted element are already removed
we can also use a multiset instead of list , its by default sorted
sir you don't even need to post the whole solution .... the way you teach the methodology to solve the sliding window ... its all done...
Solution using Dequeue
vector max_of_subarrays(int *arr, int n, int k)
{
vector vect;
deque dq;
int i, j;
i = j = 0;
while(j < n)
{
while(!dq.empty() && arr[j] > dq.back())
dq.pop_back();
dq.push_back(arr[j]);
if(j-i+1 == k)
{
vect.push_back(dq.front());
if(arr[i] == dq.front())
dq.pop_front();
++i;
}
++j;
}
return vect;
}
Can above algorithm work on following array.
1,3,-3,-1,-5,3,6,7
removing all smaller element is ok if maximum is found But for later element shouldn't maintain sorted copy?