Maximum of all subarrays of size k | Sliding Window
Вставка
- Опубліковано 2 жов 2024
- Patreon Link: / adityaverma
Video Pdf Notes And Code: / 43956990
Playlist Link: • Sliding Window Algorit...
Problem Description: www.interviewb...
Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.
Example:
Input 1:
A = [1, 3, -1, -3, 5, 3, 6, 7]
B = 3
Output 1:
C = [3, 3, 5, 5, 6, 7] .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
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
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 UA-cam one can easily pause and repeat...conceptually the video is good, but elongated without purpose
Missing the pen rotation again😅
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...
*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 😂
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:)
bhaiya graph bi start kr do....we r waiting for it..
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
Please make a series on graphs, it would help a lot.
Thanks for the previous videos...
So i have been trying to understand this one question since a day. And trust me i have watched almost every single Indian UA-cam 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 .
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.
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
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()
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
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;
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
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]
Same approach as video
O(N) Solution,
vector max_of_subarrays(int *arr, int n, int k)
{
deque dq;
vector res;
int i = 0, j = 0;
while(j < n)
{
while(!dq.empty() && dq.back() < arr[j])
dq.pop_back();
dq.push_back(arr[j]);
if(j - i + 1 == k)
{
res.push_back(dq.front());
if(arr[i] == dq.front())
{
dq.pop_front();
}
i++;
j++;
}
else j++;
}
return res;
}
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..?
can priority queue(max heap) be used?
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;
}
}
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.
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
If u have seen previous all vdo then u can start from 9:00
Thank you bro
we can use deque for O(n) complexity
LEETCODE:
class Solution {
public:
vector maxSlidingWindow(vector& array, int k) {
list list;
vector ans;
int i =0, j=0;
while(j0 && list.back()
we can also use a max heap as the data structure but the complexity will increase to nlogn
Great explanation :)
Quick side note we need to use either a list or a deque and not a queue in this question.
I literally lost my focus 😅😅😅😂😂😂😂... When u said "agar bat bheje Me nahi ghus rahi hai " .... This line. LAMO
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
THIS PROBLEM IS JUST SOLVE LIKE ANOTHER PROBLEMS THAT WE SOLVE ABOVE...
( NO CHANGE )
vector max_of_subarrays(int *arr, int n, int k)
{
// your code here
int i=0,j=0,mx=0;
vector ans;
while(j
Agar baat bheje me nhin ghus rahin 😂😂😂 23:35
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.
intuitive Explanation, Here is the code that, I have written
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque queue = new ArrayDeque();
int n = nums.length;
int[] ans = new int[n-k+1];
int idx = 0;
int s = 0;
int e = 0;
while(e < nums.length){
while(!queue.isEmpty() && queue.peekLast() < nums[e]){
queue.pollLast();
}
queue.add(nums[e]);
if(e - s + 1 < k){
e++;
} else {
ans[idx] = queue.peek();
idx++;
if(nums[s] == queue.peek()){
queue.poll();
}
s++;
e++;
}
}
return ans;
}
}
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
Love the way you explain every point, again and again; when I get confused at some point, you always explain that thing again :)
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
why he has only 2.3 lakh subscribers, mannnn he deserved more. please do subscribe guys
Sir Ji !!!!!!!.....Wapas Aao Jao UA-cam pe Please!!!!!!!!!!!!!!!!!!! Please!!!!!!!!!!!! Please!!!!!!!!!!!! Please!!!!!!!!!!!! Please!!!!!!!!!!!!
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
can anyone tell why priority queue don,t work
AAP TO HM LOG SE BHI POOR HAI EK NOTS DETE HAI VO BHI US NOTE ME ETNA RICH HOKE
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
solution using multiset
vector max_of_subarrays(int *arr, int n, int k)
{
int i=0,j=0;
multisets;
vectorv;
while(j
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)
problem link for leetcode : leetcode.com/problems/sliding-window-maximum/
problem link for gfg : practice.geeksforgeeks.org/problems/deee0e8cf9910e7219f663c18d6d640ea0b87f87/1/#
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.
Java solution :
cbsinghh.blogspot.com/2022/06/sliding-window-maximum-maximum-of-all.html
public static int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
int window_start = 0;
Deque deque = new LinkedList();
/*
* Always store window_end in deque but before doing so, remove all the smaller
* element/s than that element from the deque.
* when we do compare for removal, do peekLast() as last element will be smallest
* in queue and then if after removing(pollLast()) it, if there are other smaller
* element/s remove them before adding an element in queue.
*
*
* That will place an existing element right after bigger element and so we will
* have natural asc order in deque.
*
*/
for (int window_end = 0; window_end < nums.length; window_end++) {
while (!deque.isEmpty() && deque.peekLast() < nums[window_end]) {
deque.pollLast();
}
deque.add(nums[window_end]);
if (window_end - window_start + 1 == k) {
res[window_start] = deque.peekFirst();
// before sliding window
// 1. if the element going out is at the peek of deque, remove it
if (deque.peekFirst() == nums[window_start]) {
deque.pollFirst();
}
window_start++;
}
}
return res;
}
Thanks mate!
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;
}
class Solution:
def solve(self,arr,k):
i,j,=0,0
mx=0
ans=[]
while j
i was stuck on this problem for quite some time. thank you
@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
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. 👍
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
backtracking please
//Maximum of all subarrays of size k
/*
* input , int[] = {4 3 10 14 7 8 9 }, k=3
* output , {10 14 14 14 9 }
* */
public int[] maxiumFromSubarray(int [] ar, int k){
int i=0, j= 0;
List list = new LinkedList();
TreeMap map = new TreeMap(Comparator.reverseOrder());
while (j
I think use of Max Heap as the data structure will be simpler than maintaining the list.
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
// sliding window ques
vector ans;
int i=0,j=0;
list maxVal;
while(j
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
import java.util.*;
public class maximumOfallSubArray {
public static void main(String args[])
{
int arr[] = {1,3,1,2,0,5};
int n = arr.length;
int k = 3;
int i=0;
int j=0;
ArrayList temp = new ArrayList();
ArrayList ans = new ArrayList();
while(j0 && temp.get(temp.size()-1)
Java Code:-
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List maxOfSubarrays(List arr, int n, int k) {
Deque q = new ArrayDeque();
int i = 0, j = 0;
List res = new ArrayList();
while (j < n) {
while (!q.isEmpty() && arr.get(q.peekLast()) < arr.get(j)) {
q.pollLast();
}
q.offerLast(j);
if (j - i + 1 < k) {
j++;
} else if (j - i + 1 == k) {
res.add(arr.get(q.peekFirst()));
if (q.peekFirst() == i) {
q.pollFirst();
}
i++;
j++;
}
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
List arr = List.of(1, 3, -1, -3, 5, 3, 6, 7);
int n = arr.size();
int k = 3;
List result = solution.maxOfSubarrays(arr, n, k);
// Print the result
for (int num : result) {
System.out.print(num + " ");
}
}
}
It would be helpful if u run the code at the end of every video..
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)
I code below in Java, but I am getting TLE in test case 37/51. Can anyone help to with the code to resolve this issue.
public class SlidingWindowMaximum2 {
public static void main(String[] args) {
int[] nums = {7, 2, 4};
int k = 2;
int[] ints = maxSlidingWindow(nums, k);
for (int i : ints)
System.out.print(i + " ");
}
private static int[] maxSlidingWindow(int[] nums, int k) {
if (k == 1)
return nums;
int n = nums.length;
int i = 0, j = 0;
int[] arr = new int[(n - k) + 1];
int max;
Deque deque = new LinkedList();
while (j < n) {
if ((j - i) + 1 == k) {
if (i != 0)
deque.removeFirst();
deque.add(nums[j]);
max = findMaxInDeque(deque);
arr[i] = max;
i++;
} else {
deque.add(nums[j]);
}
j++;
}
return arr;
}
public static int findMaxInDeque(Deque deque) {
int max = deque.getFirst();
for (int i : deque) {
max = Math.max(i, max);
}
return max;
}
}
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
#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
@Aditya Verma Sir, please try to little concise, you repeat a lot same thing multiple times due to which more important thing remain less touched. Please try to little less explain same thing multiple times . If anyone want to listen any part then he can go back and see.
And also give little more focus on code. because most important is to code only.
Can we use maxheap instead of Deque????
vector max_of_subarrays(vector arr, int n, int k) {
// your code here
dequeq;
int i=0,j=0;
vectorres;
while(j
can someone tell me if we use prority queue instead of dboulble ended queue what is the harm. since we need always max element in front is't it better to use priority queue instead of deque. i used below . its working fine but leetcode some of the test cases are failing. any one can help?
private static List maximumOfAllSubarraysOfSizeK4(int[] a, int k) {
int i,j;
i = j = 0;
PriorityQueue pq = new PriorityQueue((o1, o2) -> o2-o1);
List li = new ArrayList();
while (j < a.length){
if(!pq.isEmpty() && a[j] > pq.peek()){
pq.clear();
pq.offer(a[j]);
}else{
pq.offer(a[j]);
}
if(j - i + 1 < k){
j++;
}
else if(j - i + 1 == k){
li.add(pq.peek());
if(a[i] == pq.peek() ){
pq.poll();
}
i++;
j++;
}
}
return li;
}
We can use first maximum and second maximum concept here so no list is use
If someone did it in Java using Priority queue plz share
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
int maxi = 0;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
maxi = max(arr[i], maxi);
}
if (k > n)
{
cout
Code -->
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
List ansLst = new ArrayList();
int start = 0;
int end = 0;
Deque queue = new LinkedList();
while(end < nums.length){
//calcuation --> removing all the ele which are smaller then nums[end] from array as
//they wont be the ans for any case
//if lst size goes zero then stop removing ele
while (!queue.isEmpty() && queue.peekLast() < nums[end]) {
queue.pollLast();
}
//now adding the current element
queue.offer(nums[end]);
if(end-start+1 < k){
end++;
}
else if(end-start+1 == k){
//calcuation for answer queue.front
ansLst.add(queue.peek());
//remove the calucation for start
if(queue.peek() == nums[start]){
queue.poll(); //removing the first element
}
//slide window
end++;
start++;
}
}
//System.out.println(Arrays.toString(ansLst.toArray()));
int[] ans = new int[ansLst.size()];
for (int i = 0; i < ansLst.size(); i++) {
ans[i] = ansLst.get(i);
}
return ans;
}
}
dequed;
vectorans;
int i = 0;
int j = 0;
while(j0 && d.back()
can u help me out with the left over problems on d topic u named and could not cover .....can u plz provide me problem statement of every problem left like......
Fibonacci(7)
Lis(10)
Kadane's Algorithm (6)
Dp on grid(14)
Other(5)
If you have got the problems,provide it to me also.It would be great help.
leetcode cpp soln
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
deque deq;
vector ans;
int i = 0, j = 0; // Initialize both i and j to 0
int n = nums.size();
if (k >= n) {
ans.push_back(*max_element(nums.begin(), nums.end()));
return ans;
}
while (j < n) {
while (!deq.empty() && deq.back() < nums[j]) {
deq.pop_back();
}
deq.push_back(nums[j]);
if (j - i + 1 < k) {
j++;
} else if (j - i + 1 == k) {
ans.push_back(deq.front());
if (deq.front() == nums[i]) {
deq.pop_front();
}
i++;
j++;
}
}
return ans;
}
};
Can there be any case where storing elements in the deque will fail? Instead we can store indices.
vector maxSlidingWindow(vector& nums, int k) {
vectorans;
listl;
int i = 0;
int j = 0;
while(j 0 && l.back() < nums[j]){
l.pop_back();
}
l.push_back(nums[j]);
if(j-i+1 < k){
j++;
}
//(j-i+1 == k) probably this will true
else{
ans.push_back(l.front());
if(l.size() > 0 && l.front() == nums[i]){
l.pop_front();
}
i++;
j++;
}
}
return ans;
}
in case if you want code with all test case passd !
Btw my code failed at 68th test case :
class Solution {
// Function to find maximum of each subarray of size k.
max_of_subarrays(arr, n, k) {
var arr2 = [];
for (let i = 0; i < n - k + 1; i++) {
var temp=0;
for (let j = i; j < k + i; j++) {
if(arr[j]>temp){
temp = arr[j]
}
}
arr2.push(temp);
}
return arr2;
}
}
could anybody tell me the reason :)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque q = new ArrayDeque();
int i=0, j=0, ptr=0;
int n = nums.length;
int[] res = new int[n-k+1];
while(j
What is time complexity of this approach?
Since he is using while loop delete ele...is it still O(n)?
vector max_of_subarrays(int *arr, int n, int k)
{
// to store the final vector array
vector v;
int left = 0, right = 0, maxi = INT_MIN;
list ans;
while(right < n){
//calculations
ans.push_back(arr[right]);
if(right - left + 1 < k){
right++;
}
else if(right - left + 1 == k){
//ans cal
maxi = *max_element(ans.begin(), ans.end());
v.push_back(maxi);
//slide
if(arr[left]
can we store in 2 variables max1 and max2 and update both of them?
is this code correct
class Solution {
public int[] maxSlidingWindow(int[] A, int B) {
if(A.length==1) return new int[]{1};
int i=0;
int j=0;
int lar1=-19000;
int lar2=-19000;
int N = A.length;
int [] ans = new int[N-B+1];
while(j lar1)
{
lar2 = lar1;
lar1 = A[j];
}
else if (A[j] > lar2 && lar2 < lar1)
{
lar2 = A[j];
}
if(j-i+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.
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()
Can't we use Priority Queue with max heap to avoid this manual work of maintaining queue?
20:57…one line that addressed my whole doubt..ye 1 kaam ayega ki nahi👌🏻
vectorans;
dequedq;
int i=0,j=0;
while(j
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
class Solution
{
public:
vector max_of_subarrays(int *arr, int n, int k)
{
// your code here
int start = 0;
int end = 0;
priority_queue pq;
vector ans;
while (end < n)
{
while (!pq.empty() && pq.top() < arr[end])
{
pq.pop();
}
pq.push(arr[end]);
if ((end - start + 1) < k)
{
end++;
}
else if ((end - start + 1) == k)
{
ans.push_back(pq.top());
if (arr[start] == pq.top())
{
pq.pop();
}
start++;
end++;
}
}
return ans;
}
};
please help i have implemented it using max heap but it is passing only 30 test case out of 61
thanku bhaiya...... after watching it mre than 5 times i got the intuition
your channel deserves to be hyped !!! tysm(happy tears)
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?
please Aditya sir make video on graph ,trees, backtracking we are waiting for upcoming lectures on mentioned topic above
Pehla video h jo mujhe bilkul samjh nhi aa rha h... 3-4 baar dekh chuka hu😢
Explained Approach handling edge case can be implemented as:-
vector maxSlidingWindow(vector& A, int B) {
vector ans;
if(A.size()
Agar baat bheje mai nahi ghush rahi hai to bheje mai ghusao kyunki isse easy explanation nahi ho nahi sakta🌚