Shortest Subarray with Sum at Least K | Leetcode
Vložit
- čas přidán 9. 07. 2024
- OUR DSA COURSES:
🟢DSA Interview preparation Course: • DSA Crash Course Expla...
🟠DEMO class: • Reservoir Sampling | U...
This video explains a very important programming interview problem which is to find the shortest subarray with a sum of at least K. The prerequisite for solving this is to watch my video on leetcode #209 Minimum Size Subarray Sum. I have first explained the problem statement and then shown why the simple 2 pointer sliding window technique doesn't work. I have also explained how to choose the data structure and why did we take Deque and not a stack. Finally, I have shown the intuition and dry run along with code walkthrough.
CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
======================================PLEASE DONATE=============================
🧡 SUPPORT OUR WORK: / techdose
💚 UPI-ID: surya.kahar@ybl
💞JOIN Membership: / @techdose4u
==============================================================================
INSTAGRAM : / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
USEFUL LINKS:-
🟠Must do TIPS to ACE Virtual Interview: • 🔴Must do Tips to ACE y...
🟢Best strategy to excel your coding interview: • 🔴Best strategy to exce...
🟡Get your dream job in 1 month: • 🔴Get your dream job in...
🔵How to crack dream job in just 2 months: • How to crack dream job...
🟣7 Days DSA plan: techdose.co.in/7-days-dsa-che...
RELATED LINKS:
Minimum Size Subarray Sum | Leetcode #209: • Minimum Size Subarray ...
CODE LINK: gist.github.com/SuryaPratapK/...
Improper explanation
Just got an offer from amazon.
Thank you so much for your videos.
They helped me a lot when grinding leetcode🙏🙏
Can you plz tell time gap between 2nd round and 3rd round bcoz I cleared 2nd round 1.5 months ago but still haven't got round 3 mail and also i haven't got rejection mail.
in this provided code he made the dqueue deque dq; with integer data type replace it with long long new test case has been added in leetcode so due to overflow you will get wrong ans . so use long long
Thanks for being a great teacher!
Such an elegant and beautiful explanation. Thank you Surya Pratap 🙏🏽
Hello Sir, if possible make a playlist of all important questions for interviews.This would help the community a lot!
Your way of explanation is phenomenal that's why I am requesting you to provide these super helpful playlists here on youtube so that it helps those who can't afford resources.
Congratulations sir 🎉 for getting AIR 1 in Google kick start
Such a smooth explanation !
Sir you said , you only pop when sum is >= target , what if the array is [-12,-22,-33,5] and target is 4 , how would it work in this case ?
in the first solution sliding window one which you said it won't work. if the right till the end, why not keep the left index and doing a seperate for loop start from this left index and shrinking again?
Such amazing explanation 😁😁
🔥🔥🔥
Sir, on which software(Blackboard) are you writing this??
Hey, did you get it?
@@guneetmalhotra01 nope
Nice explanation sir
I can't understand intuition behind this approach!! I have read many articles on leetcode also, but still...
I have not looked at Leetcode. I guess there are at least 1000 problems. How do one remember the logic, even after practicing or understanding the logic, I do tend to forget things. Guess its sign of aging :(
nice explanation sir!!
Why monotonocity is preserved? What happens when we include negatives
Can anyone tell me which blackboard software is this?
Calculating Max Sum of Array with the following condition, If A[i] element contributing in max sum,than you can't consider A[i]-1 and A[i]+1 element for max sum contribution, if present in array .
Note: Elements of the array can be repeated multiple times. It's unsorted. It can have 1 to n number of element.
eg:
int A[ ]={1,6,7,1,2,3,3,4,5,5,5,6,9,10};
If I consider 10 as contributing max sum, I can consider 9 and 11. (Here 11 is not present but 9 is present still we can’t consider it).
If I consider 5 (total max sum contribution 5*3) but can’t consider 4 and 6.
I have tried sorting and storing index and count in the ordered map. Also try to compare with unbounded knapsack criteria.
Still, I was struggling with an optimal and clear idea to calculate. Any idea how to approach it .
Consider storing the elements into an array (hashing) and apply house robber (kind of, but the approach would be similar) on this freqency Array
From the example, when we insert (4,3) why do we have to leave (2,0) to deque? As subarray should be contiguous, doesn't it also have to removed as its left to newly considering index 3?
Think of this case. [2,-1,2], k = 3 . Now we will need to keep the index of first 2 in the array as well to get monotonically increasing value of complete subarray.
@@harigovind11 Thanks for the explanation. Your example gave me the point I was missing.
Code not workingon leetcode now as few more test cases added
What is the intuition behind this algorithm and why monotonous increasing will work here, can anybody please explan?
Why popping elements from the deque won't affect the result?
💥💥
:)
I love you bro
What is the name of this tool (colour pens) which is your using to write on blackboard?
Clean Explanation. Thanks!
Sir what about binary search approach when binary search on possible lengths and finding if this length is possible or not by sliding window, why this approach is giving me wrong on 87/97
The numbers are negative also in array thus thinking that increasing window size would increase sum is wrong
Thanks for the solution, but what is the point of keep [2,0] and [4,3] in the queue, what does it represent ?, isn't it non-contiguos.
Think of this case. [2,-1,2], k = 3 . Now we will need to keep the index of first 2 in the array as well to get monotonically increasing value of complete subarray. So basically we can remove from deque only when the sum gets greater than k.. In other cases we should not delete it because it might be of use.
I'm new to programming, can anyone of you tell me which is the best way to start learning coding? And best platform(which has the complete content)? Any good Websites?/video courses?
Stopped making new videos?
Great explanation with clear visualization.
How would this logic work out for [2, -1, 2] and target = 3 ? As per the analysis, the final queue is [ (1,1) , (3,2)]. But the answer is 3.
Hi, can you tell me which is the best way to start learning coding? And best platform(which has the complete content)? Any good Websites?/video courses?
i am also stuck on then same case, did you find any solution for it?
Guys even if leetcode test case pass , this approach is wrong for generally solving the questions, thousands of test case will fail
it doesn't make sense if you only explains a single example, also you are saying delete it if still the sum is greater but in end when 18-8
Not able to get the case with above approach is [5, 7, -12, 20, 5, 2, 1, 23] target =8 minimal subarray is -12, 20
minimal subarray would be 20 here cause it is greater than 8. It is giving right answer, I checked on leetcode.
Bro Did you Find any Valid answer
@@sakshigupta7616then solve for this [7,-1,6,1,1,1]
K= 9
cool solution but not upto mark in explaining ,
Not so intuitive