Leetcode - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

  Рет қаралды 29,352

Fraz

Fraz

Күн бұрын

Пікірлер: 63
@aishwat
@aishwat 4 жыл бұрын
5:16 you mean greater than one, anyway great explanation!
@alexnice2221
@alexnice2221 3 жыл бұрын
Amazing solution. I learned something new. Thank you Sir 😄 I know "sliding window" plus a "Hash" and a " counter" can be used to find longest subarray with k distinct elements Now you taught me that sliding window plus "min" and "max" deque can be used to find longest window with absolute difference less than k
@alexnice2221
@alexnice2221 3 жыл бұрын
I love that min and max queue technique with the sliding window. Also that deque technique is also used when finding the max or min value in each subarray of size K in an array O(n) time
@studyaccount794
@studyaccount794 2 жыл бұрын
Great explanation. This is one of the harder monotonic stack/deque problems in my opinion.
@hyeonwoopark428
@hyeonwoopark428 Жыл бұрын
OMG You are the best! I love learning this technique!
@bizdep6237
@bizdep6237 3 жыл бұрын
Why can't we use min and max function to calculate min of (start and end) and max of (start and end). I am trying to understand why we need dequeue and i also know this is the right approach as my way isn't giving the right output. Here is my python code, from your algorithm, it looks like max and min changes depending on whatever the max and min value of start and end variable is maxim,minim = nums[0],nums[0] maxlen = 0 start,end = 0,0 while end < len(nums): maxim = max(nums[start],nums[end]) minim = min(nums[start],nums[end]) if (maxim-minim) > limit: start += 1 else: end +=1 maxlen = end-start+1 return maxlen
@AnshMehtaGR8
@AnshMehtaGR8 4 жыл бұрын
Why time complexity of deletion considered to be O(1) for deleting multiple elements from the deques. What if there are N elements to removed from the deque?
@mohammadfraz
@mohammadfraz 4 жыл бұрын
Actually at most n elements will be inserted or removed in total. So it would be O(N)
@akhilkumaramarneni8153
@akhilkumaramarneni8153 4 жыл бұрын
in the first explanation, if we take input [4,8,5,1,7,9] ur output is 6 but excepted is 3. u r comparing only with min and max elements.
@sharu1029
@sharu1029 4 жыл бұрын
what is the limit here?
@alexgillespie1098
@alexgillespie1098 2 жыл бұрын
This should be a leetcode hard especially considering "Sliding Window Maximum" is a hard, and this problem is much more difficult than that one
@dailymemes2512
@dailymemes2512 3 жыл бұрын
Can we use set we insert into set begin () will give smallest and end()-1 will give maximum
@sumitbisht4161
@sumitbisht4161 2 жыл бұрын
Clear and concise explanation 👍🏻
@xesfa
@xesfa 2 жыл бұрын
such an amazing explaination, thank you!
@code7434
@code7434 4 жыл бұрын
so sliding window kind of approach basically
@dhanushr2326
@dhanushr2326 6 ай бұрын
What will your algorithm output for this input [10, 1, 2, 1, 7, 2] for k=5 It will be 4 , which is wrong.
@DiaryOfMuhib
@DiaryOfMuhib 4 жыл бұрын
Awesome explanation. Make more videos like this
@willturner3440
@willturner3440 4 жыл бұрын
Can also use sliding window
@kopparthisai2918
@kopparthisai2918 4 жыл бұрын
@Lead Coding Why are we incrementing s by only 1 at everystep. Other sliding window problems we tend to squeez the sliding window by continiously increamenting s by 1.
@testbot6899
@testbot6899 2 жыл бұрын
This question was asked in Facebook screening round
@yuganderkrishansingh3733
@yuganderkrishansingh3733 4 жыл бұрын
Hye bro. Good video. Enjoyed it. Pls keep making more such videos.
@mohammadfraz
@mohammadfraz 4 жыл бұрын
Sure
@frogger832
@frogger832 4 жыл бұрын
The two deques are so simple yet the concept is hard to understand.
@alexnice2221
@alexnice2221 3 жыл бұрын
Its an incredibly powerful technique because many interviews have difficult array problems that need to be solved in 0(n) time. Please check the question "find the max or min value in each subarray of size K n an array, in O(n)" It would be mind boggling when you get the solution
@MustafaKhan-qk9ls
@MustafaKhan-qk9ls 2 жыл бұрын
What if we wanna get non continuous subarray with difference less than equal to limit???
@Siddharthpratapsingh
@Siddharthpratapsingh 4 жыл бұрын
No logical flow of thought process. Deques just pop up out of nowhere. Where is the recurrence relation?
@2lazydba
@2lazydba 4 жыл бұрын
Thats cos u havent practiced enuf and want everything spoon fed tat too for free
@ShwetaSingh-yp4ok
@ShwetaSingh-yp4ok 4 жыл бұрын
thanks for the solution. really good explanation.
@nguyendangkhoa621
@nguyendangkhoa621 Жыл бұрын
thanks sir, u helped me a lot
@code7434
@code7434 4 жыл бұрын
issue is we need index corresponding to minimum and maximum , m i right? so why not just use a pair , actually i dont want to use deque
@yuganderkrishansingh3733
@yuganderkrishansingh3733 4 жыл бұрын
think duplicates. How do u even know what is the new minimum/maximum is once the window changes? If there are multiple instances of these then it will be quite inefficient if u r iterating through the whole window to check again and again that what's the new min or max. Better to store them in some DS which is optimal.
@lifehacks9450
@lifehacks9450 4 жыл бұрын
Amazing work sir
@yashgupta-fk3zc
@yashgupta-fk3zc 2 жыл бұрын
bhaiya what if we use stack for min and max element
@aryan__o
@aryan__o Жыл бұрын
Thank you Sir 😘
@haidisaid6689
@haidisaid6689 3 жыл бұрын
how to do this task using dynamic programming?
@aleyummusic
@aleyummusic 4 жыл бұрын
Why do remove all elements at 5:49?
@fluffy_raptor
@fluffy_raptor 3 жыл бұрын
Finally have the answer. This took me forever to understand as no one ever explained it. input: [74,42,85,81,55] limit: 4 variables at every step left pointer | minheap | maxheap| right pointer 0 [74] [-74] 0 0 [42, 74] [-74, -42] 1 1 [42, 74] [-42] 1 1 [42, 74, 85] [-85, -42] 2 2 [74, 85] [-85, -42] 2 3 [74, 85] [-42] 2 3 [74, 85, 81] [-81, -42] 3 4 [74, 85, 81] [-42] 3 4 [55, 74, 81, 85] [-55, -42] 4 [55, 74, 81, 85] [-55, -42] our answer: 1 correct answer: 2 If you look at line seven in the 'variables at every step' portion you will see if we don't delete the excess numbers we will sometimes compare the wrong numbers. We should be comparing 85-81 (which is less then four) as 74 was made redundant when we added 42 to the min heap as 42 is smaller and came after 74. compare that to what should be printed at every step left pointer | minheap | maxheap| right pointer 0 [74] [74] 0 0 [42] [74, 42] 1 1 [42] [42] 1 1 [42, 85] [85] 2 2 [85] [85] 2 2 [81] [85, 81] 3 2 [55] [85, 81, 55] 4 3 [55] [81, 55] 4 4 [55] [55] 4 You can now see at line seven we are comparing 81 to 85 which is 4 which is equal to or less then our limit so the answer would be 2, the correct answer, instead of our original 1. Again the issue was because we still had redundant numbers such as 74 in our heaps that should of been removed.
@sourabhkhandelwal689
@sourabhkhandelwal689 4 жыл бұрын
Aren't what you are using called MonoQueues(Monotonic Queues)?
@mohammadfraz
@mohammadfraz 4 жыл бұрын
Yes
@sachinsain3884
@sachinsain3884 2 жыл бұрын
it was asked in uber dsa round
@abhaytiwari1615
@abhaytiwari1615 4 жыл бұрын
Can you please tell me how you got the hint that we have to use *deque* data structure here? Please reply asap...i have my placement test next week.
@mohammadfraz
@mohammadfraz 4 жыл бұрын
It's based on practice. You can refer to the microsoft playlist and practice questions from there, for placements
@abhaytiwari1615
@abhaytiwari1615 4 жыл бұрын
@@mohammadfraz okay. Thanks for the reply 👍
@snowwhite4457
@snowwhite4457 3 жыл бұрын
my horses name is boris
@Nani-rp5dr
@Nani-rp5dr 3 жыл бұрын
Super sir🔥
@mohammadfraz
@mohammadfraz 3 жыл бұрын
Thanks ❤️
@yashthakkar4499
@yashthakkar4499 4 жыл бұрын
excellent video keep it up
@wuschelbeutel
@wuschelbeutel 4 жыл бұрын
Good video. Side comment: Deque is pronounced just like "deck."
@mohammadfraz
@mohammadfraz 4 жыл бұрын
Thanks a lot 😊
@shreya-rs1fr
@shreya-rs1fr 3 жыл бұрын
e++ should be at the end. } else{ ans = max(ans, (e-s+1)); } e++;
@aleyummusic
@aleyummusic 4 жыл бұрын
What program are you using to draw?
@mohammadfraz
@mohammadfraz 4 жыл бұрын
I am using a writing tab Software is Microsoft one note
@aleyummusic
@aleyummusic 4 жыл бұрын
@@mohammadfraz ty
@pvchio
@pvchio 4 жыл бұрын
we can actually use two variables for min and max
@mohammadfraz
@mohammadfraz 4 жыл бұрын
Can you tell how ?.
@pvchio
@pvchio 4 жыл бұрын
@@mohammadfraz in JS var longestSubarray = function(nums, limit) { let size = 0; for (let i = 0; i < nums.length; i++) { let min = nums[i]; let max = nums[i]; for (let j = i; j < nums.length; j++) { min = Math.min(min, nums[j]); max = Math.max(max, nums[j]); if (Math.abs(min - max)
@mohammadfraz
@mohammadfraz 4 жыл бұрын
@@pvchio this will not pass the constraints as this is O(N^2)
@sourabhverma0
@sourabhverma0 4 жыл бұрын
@@mohammadfraz hey thanks for this, I now know there's something like dequeus. I did find a solution with dequeues too which got accepted. github.com/black-shadows/InterviewBit-Topicwise-Solutions/blob/master/Codersbit/Longest%20Subarray%20Difference.cpp
@vinoddiwan5792
@vinoddiwan5792 4 жыл бұрын
Which software you are using to write on black screen.
@mohammadfraz
@mohammadfraz 4 жыл бұрын
one note
@code7434
@code7434 4 жыл бұрын
:)
Twin Telepathy Challenge!
00:23
Stokes Twins
Рет қаралды 96 МЛН
This Game Is Wild...
00:19
MrBeast
Рет қаралды 154 МЛН
The IMPOSSIBLE Puzzle..
00:55
Stokes Twins
Рет қаралды 167 МЛН
My Brain after 569 Leetcode Problems
7:50
NeetCode
Рет қаралды 2,7 МЛН
Reality of my 62LPA package
10:06
Fraz
Рет қаралды 469 М.
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 688 М.
Max Consecutive Ones (LeetCode 1004) | Full Solution w/ animations
14:41
Twin Telepathy Challenge!
00:23
Stokes Twins
Рет қаралды 96 МЛН