It s a bit confusing, when you say a deque has two properties, mentioning first one that its always sorted. It sounded like you are mentioning that it is one of the properties of data structure. You should clearly specify that it is sorted here in this case! We keep it sorted in THIS CASE. :) Good work otherwise. Your videos are very nice.
I am a fan of you man. This video or your system design videos or any other videos you make, all have excellent content, and the best part is the way you explain, so easy to understand. I have solved this question, earlier as well, but couldn't solve it using deque again when I revisited it. I think, I won't forget it this time. :). Keep up the good work.
I appreciate your enthusiasm and dedication. Keep up the good work. It's very inspiring. PS: Keep smiling. I wonder what makes you so happy. Regardless its awesome😉
The worst case time complexity for this question using dequeue could be more detailed: O(n + n) // for enqueue and dequeue of each element + O((n/R - 1)* R) // for the repetition of accessing 'new element' to be compared with 'existing elements' in queue; where there would be n/R - 1 such 'new elements' in worst case and R 'existing elements' in queue for each of those new elements in worst case. Total: O (n + n + (n/R - 1)* R) = approx O(n) (The second part is where normally people think that wouldn't this cause the worst time complexity to be O(nR)) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Example 1: // worst case R = 10, n = 30 array: 10 9 8 7 6 5 4 3 2 1 11 10 9 8 7 6 5 4 3 2 12 11 10 9 8 7 6 5 4 3 For each of 11(first occurrence) and 12, there would be ten existing elements in queue to be compared with 11 and 12. Hence, 11 and 12 are accessed ten times each. Here, n/R - 1 = 30/10 - 1 = 2 elements, which are 11 and 12. These would be compared with R existing elements in queue: 2 * R = 2 * 10 = 20 Example 2: A different case could be (n = 11, R = 10): 10 9 8 7 6 5 4 3 2 1 11 Here, since only 1 element, 11, is getting repeatedly accessed with ten existing elements in queue, this would not be worser than the previous case, making the previous case the worst case. Please correct if wrong ^ _ ^
This guy has excellent and deep understanding of data structures and algorithms and with good teaching skills he has nailed it to explain these concepts which is very helpful for beginners like me. Great work brother keep it doing !
Is it pure O(n) because each time you add an item to the deque you scan all items on the left of the current element in the deque to see if any element is smaller than the current element. Thus depending upon the size of the queue you are doing multiple operations per element.
Hey Abhishek! You can have a look at the amortized complexity video to get an idea. The total cost of all operations is still O(n). ruclips.net/video/MTl8djZFWE0/видео.html
How do you convince yourself about the correctness of this technique. What is the invariant that is being maintained? Some of the points you could speak about. Good video
Nice Video. However Complexity is O(N*K) not O(N), as while removing obsolete elements we need to search index for those elements. O(N) can be achieved by checking the outgoing element in sliding window with head of Deque. In case of duplicates we need to store both instances.
Yes. One way would be to negate all the elements: a[i] = -1*a[i]. Then the max at every range will actually be the min. When printing the answer, you could print -1*answer.
Thats an interesting problem. Did you try the editorial on codechef: discuss.codechef.com/questions/92702/schedule-editorial abx_2109 has a unique solution to this. Have a go at it, and if you still need help, I will be happy to make a video on this :-)
Basically you would have {5,4,3,2,1,6} as one sub array and {4,3,2,1,6,7} as another sub array So the output would be 6,7 (Maximum of first sub array and maximum of second sub array)
It s a bit confusing, when you say a deque has two properties, mentioning first one that its always sorted. It sounded like you are mentioning that it is one of the properties of data structure.
You should clearly specify that it is sorted here in this case! We keep it sorted in THIS CASE.
:) Good work otherwise. Your videos are very nice.
That's true 😊
This explanation is so much better than the 'geeks for geeks' video
Thank your in the name of all the viewers for this great explanation!
Cheers 😁
I am a fan of you man. This video or your system design videos or any other videos you make, all have excellent content, and the best part is the way you explain, so easy to understand. I have solved this question, earlier as well, but couldn't solve it using deque again when I revisited it. I think, I won't forget it this time. :).
Keep up the good work.
Thank you!
Very well explained,I am shocked such a easy concept exists then that of this sparse table!!
Thank you for such an easy explanation of deque with a great use case.
why so many dislikes ? this was the perfect video I was looking for
I appreciate your enthusiasm and dedication. Keep up the good work. It's very inspiring.
PS: Keep smiling. I wonder what makes you so happy. Regardless its awesome😉
Thanks Jigar :-D
He is the kind of guy you would like as your team lead in your company
Cheers :D
The worst case time complexity for this question using dequeue could be more detailed:
O(n + n) // for enqueue and dequeue of each element
+
O((n/R - 1)* R) // for the repetition of accessing 'new element' to be compared with 'existing elements' in queue; where there would be n/R - 1 such 'new elements' in worst case and R 'existing elements' in queue for each of those new elements in worst case.
Total: O (n + n + (n/R - 1)* R) = approx O(n)
(The second part is where normally people think that wouldn't this cause the worst time complexity to be O(nR))
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Example 1: // worst case
R = 10, n = 30
array: 10 9 8 7 6 5 4 3 2 1 11 10 9 8 7 6 5 4 3 2 12 11 10 9 8 7 6 5 4 3
For each of 11(first occurrence) and 12, there would be ten existing elements in queue to be compared with 11 and 12. Hence, 11 and 12 are accessed ten times each.
Here, n/R - 1 = 30/10 - 1 = 2 elements, which are 11 and 12.
These would be compared with R existing elements in queue: 2 * R = 2 * 10 = 20
Example 2:
A different case could be (n = 11, R = 10): 10 9 8 7 6 5 4 3 2 1 11
Here, since only 1 element, 11, is getting repeatedly accessed with ten existing elements in queue, this would not be worser than the previous case, making the previous case the worst case.
Please correct if wrong ^ _ ^
We have used DEQueue here and not Queue because we have to pop elements from both sides, although we are inserting elements from the back only.
fairly impressed by your passion!!!!! really nice explanation. Thanks a lot :)
Thanks Yanling :-)
This guy has excellent and deep understanding of data structures and algorithms and with good teaching skills he has nailed it to explain these concepts which is very helpful for beginners like me. Great work brother keep it doing !
Is it pure O(n) because each time you add an item to the deque you scan all items on the left of the current element in the deque to see if any element is smaller than the current element. Thus depending upon the size of the queue you are doing multiple operations per element.
Hey Abhishek! You can have a look at the amortized complexity video to get an idea. The total cost of all operations is still O(n).
ruclips.net/video/MTl8djZFWE0/видео.html
thanks. I will look at it.
Gaurav Sen hi Gaurav, you mean you are trying to say, you remove from last too?
Vijay Anand Yes we do. 'Poll last' does that.
How do you convince yourself about the correctness of this technique. What is the invariant that is being maintained? Some of the points you could speak about. Good video
Finally, DEQUE understood.......
Remove first and Insert Last? Couldnt that be done with a Queue as well? Not sure why you need a Deque Here.
what if the array isn't sorted, if we will sort it, the output will change
Nice Video. However Complexity is O(N*K) not O(N), as while removing obsolete elements we need to search index for those elements. O(N) can be achieved by checking the outgoing element in sliding window with head of Deque. In case of duplicates we need to store both instances.
Kindly have a look at stackoverflow.com/a/60108480/5649620
I am not sure u need dequeue here. U are using only Queue - Remove first and Insert Last?
We are removing from the front too :)
Why is the compelexity of this algorithm is O(n) it should be O(n*k) please explain.
What if you use a PQ of size R ?
is deque always sorted in nature? Is it a property of the data structure?
no, it is sorted here in this case!
but how will we find top element in bst ? which will be max
thanks, amazing explanation.
Thanks for your teaching bro😘.
Deque starts around 3:40
nice video! if possible then plz explain with a little larger size of array. :)
Code implementation with detailed comments
github.com/akuchotrani/CodingInterviewQuestions/blob/master/Leetcode/Leetcode%20Problem%20239%20Sliding%20Window%20Maximum.txt
Great work man
if i want to get the minimum at the very first index the i cant....is there any way to do this?
Yes. One way would be to negate all the elements: a[i] = -1*a[i].
Then the max at every range will actually be the min. When printing the answer, you could print -1*answer.
got it thanks!
if possible plz make videos on graph problems!
please do video on cooking schedule from mar17 long challenge
Thats an interesting problem. Did you try the editorial on codechef:
discuss.codechef.com/questions/92702/schedule-editorial
abx_2109 has a unique solution to this. Have a go at it, and if you still need help, I will be happy to make a video on this :-)
It's confusing. I couldn't understand.
It seems you are confused for BST approach
And atleast take a larger array where you show the value of BST
Size of two doesn't make any sense
When you are explaining something you REALLY should slow down a bit. At some point I had to activate the subtitles.
awesome work bro
Thanks!.
very very thx bro @gaurav sen
what if a[]=5,4,3,2,1,6,7 and k=6
Basically you would have {5,4,3,2,1,6} as one sub array and {4,3,2,1,6,7} as another sub array
So the output would be 6,7 (Maximum of first sub array and maximum of second sub array)
Nicely explained buddy
Thanks!
I think this is priority queue
If possible do a video on Trie data structure.
Hi Sourik!
Will put that data structure on the list, I have an interesting problem in mind for that :-D
awesome Teaching Man
Very clearly explained :)
Thanks Phanesh!
got it!.. thanks
Nice Tutorial Gaurav :) If possible please make video on Multi-way tree, Happy Coding
Nice suggestion Akash!
I am in the process for making a tutorial on Tries. That would be a case of multi-way trees, so putting that in priority!
Audio n video quality needs to be improved.
The explanation is totally confusing.
It's pronounced as "DECK"
awesome explanation. please go a bit slow :)
I hope my pace has improved now 😋
really nice .....
Thanks!
super bro
Thanks!
I see what you did there 😂😂
all good coders are skiny
It's pronounced 'deck'.
Why you motivate to make videos??
😁
Need a video on it...or personal talk..