Good one sir, I solved 850+ questions on leetcode with 350+ days streak Still selected for 3.5LPA in TCS Feeling sad but i am still motivated and consistent that i will do Big someday Thanks for posting videos regularly
This was my approach for this question but failed to handle negative values : class Solution { public: int shortestSubarray(vector& nums, int k) { int len = INT_MAX; int l = 0; int r = 0; int n = nums.size(); int sum = 0; while(r < n) { sum+=nums[r]; while(sum >=k) { sum-=nums[l]; len = min(len,r-l+1); l++; } r++; } if(len==INT_MAX) { return -1; } return len; } };
Hi Mazhar. Thanks for the video. @codestorywithMIK Just a *small suggestion/request* to add a unique hashtag or keyword to your video title. When stuck with any leetcode question, i often look for your explanation video but due to long channel name it is slightly cumbersome to find the video quickly. As of now, i personally use your git repo to find code snippets and related explanation videos. But if possible, you can include a simple and quick hashtag to your video or any content in general so that we can find your videos quickly. This might help in expanding the reach of channel too as more and more viewers will do organic searches for your hashtag. Rest, keep doing the great work! God bless you!
So sir ...You mean to say that suppose we wish to move ith pointer ...its possible that cumSum is larger or greater and we cannot obtain sum >= k and also if we get there maybe some smaller cumSum ahead of i and if we subtract it with that lesser cumSum we may get sum >= k ..SO we keep track of previous elements in increasing order so that we have min or less element to check with ( which gives higher chances of getting sum >= k ) and then for larger and again larger so as to see if we can shrink ... Am I Correct ?? IF NOT please correct sir 🙏🏻🙏🏻
Are aise samjho. nums = {84, -37, 37, 40, 95} cumSum = {84, 47, 84, 124, 219} Let's say you are index j = 4, where cumSum is 219 >= k Now, you want to shrink the window. If you notice if you shrink and remove index 0 from left side i.e. 84 Then subarray sum from index 1 to index 4 will be = cumSum[j] - cumSum[0] = 219 - 84 = 135 But if you notice, even if you shrink the window further and remoce index 0 and index 1 from the window, you get the same answer= cumSum[j] - cumSum[2] = 219 - 84 = 135 So there was no point of keeping the first 84 because there was a dip from 84 to 47 and we can get sum >= k further also which will be even shorter subarray. Hope this is clear
Can't we keep count of negative no. We encounter in window if there is negative no. That means there is chance that sum would get increased hence we can shift the window towards left ..
As soon as j reaches 50, the cumulativeSum[j] will become = 100 And if you notice I have put a check that if cumulativeSum[j] >= k result = min(result, j+1) So result becomes = 3 So we won’t miss that case also where we reach sum >= 100 here in this example That was a good example. Thanks for this Qn ❤️🙏
yes, but it will only give TLE. But you must start with Brute force (82/98 testcase passed) Java Brute force: class Solution { public int shortestSubarray(int[] nums, int k) { int len = 10000000; //any max number //check each subarray for(int i = 0; i < nums.length; i++){ for(int j = i; j < nums.length; j++){ int sum = 0; //window sum for(int s = i; s = k){ len = Math.min(len, j - i + 1); } } } return len == 10000000 ? -1 : len; } }
Anyone need more clarity on why first 84 was removed from deque as soon as we saw a dip from 84 to 47. Here is more points to get more clarity. nums = {84, -37, 37, 40, 95} cumSum = {84, 47, 84, 124, 219} Let's say you are index j = 4, where cumSum is 219 >= k Now, you want to shrink the window. If you notice if you shrink and remove index 0 from left side i.e. 84 Then subarray sum from index 1 to index 4 will be = cumSum[j] - cumSum[0] = 219 - 84 = 135 But if you notice, even if you shrink the window further and remoce index 0 and index 1 from the window, you get the same answer= cumSum[j] - cumSum[2] = 219 - 84 = 135 So there was no point of keeping the first 84 because there was a dip from 84 to 47 and we can get sum >= k further also which will be even shorter subarray. Hope this is clear. Thanks to MIK for improving my thinking skills.
Why using Dequeue cant we use Stack here?As we can get increasing Sequence using Stack..What is the special advantage of using Double ended Queue ?it only allows insertion and deletion from both start and end
The only benefit is that you can shrink the window from left side which is the requirement of this problem. You can pop from left side and push from right side.
Are aise samjho. nums = {84, -37, 37, 40, 95} cumSum = {84, 47, 84, 124, 219} Let's say you are index j = 4, where cumSum is 219 >= k Now, you want to shrink the window. If you notice if you shrink and remove index 0 from left side i.e. 84 Then subarray sum from index 1 to index 4 will be = cumSum[j] - cumSum[0] = 219 - 84 = 135 But if you notice, even if you shrink the window further and remoce index 0 and index 1 from the window, you get the same answer= cumSum[j] - cumSum[2] = 219 - 84 = 135 So there was no point of keeping the first 84 because there was a dip from 84 to 47 and we can get sum >= k further also which will be even shorter subarray. Hope this is clear
In que you won’t be able to pop from behind to maintain monotonic nature. Notice that in order to make it increasingly monotonic we will have to pop from behind. Also to shrink the window, we need to pop from front also. So deque provides both functionalites
Good one sir,
I solved 850+ questions on leetcode with 350+ days streak
Still selected for 3.5LPA in TCS
Feeling sad but i am still motivated and consistent that i will do Big someday
Thanks for posting videos regularly
congrats man. don't worry it's the start. you will get to your goal. have faith and keep grinding.
bhai konse college se ho.
Hey can you can share your linkedin ID
Congrats man celebrate every moment although your output is not equal to your effort but soon you will get to your goal
contest rating kitna hai?
Aaj monotonic stack/queue/deque ki need samaj ayi, thanks ❤
Thnx bro, loved the approach. Solved the medium level one without thinking but couldn't solve when negtive numbers were involved
This was my approach for this question but failed to handle negative values : class Solution {
public:
int shortestSubarray(vector& nums, int k) {
int len = INT_MAX;
int l = 0;
int r = 0;
int n = nums.size();
int sum = 0;
while(r < n)
{
sum+=nums[r];
while(sum >=k)
{
sum-=nums[l];
len = min(len,r-l+1);
l++;
}
r++;
}
if(len==INT_MAX)
{
return -1;
}
return len;
}
};
0:45 yes sir and these are those people who are themselves going nowhere..
Indeed 🙏
amazing sir
legend is here.
i solved leetcode-209 as well. thanks to you
thank you sir . awesome explanation.
i eactly got stuck at the -ve part part the test was exactly the i was stuck 84 -37 32 40 95
Hi Mazhar. Thanks for the video.
@codestorywithMIK Just a *small suggestion/request* to add a unique hashtag or keyword to your video title. When stuck with any leetcode question, i often look for your explanation video but due to long channel name it is slightly cumbersome to find the video quickly. As of now, i personally use your git repo to find code snippets and related explanation videos.
But if possible, you can include a simple and quick hashtag to your video or any content in general so that we can find your videos quickly. This might help in expanding the reach of channel too as more and more viewers will do organic searches for your hashtag.
Rest, keep doing the great work!
God bless you!
Hi there,
I appreciate your feedback. Thank you so much.
Let me try to add #MIK from now onwards.
That might help ❤️🙏
Thanks a lot bhaiya ❤❤
waiting for this video
good afternoon bhaiya ..
Brother your explanation is awesome keep it up bro
You explain great,
But plz try to upload solutions of Leetcode contest at least of only EASY level
Yes definitely. Actually i always travel during weekends to take break.
I will try to upload them as well.
Thank you for your kind words ❤️🙏
Was waiting. Thanks a lot
So sir ...You mean to say that suppose we wish to move ith pointer ...its possible that cumSum is larger or greater and we cannot obtain sum >= k and also if we get there maybe some smaller cumSum ahead of i and if we subtract it with that lesser cumSum we may get sum >= k ..SO we keep track of previous elements in increasing order so that we have min or less element to check with ( which gives higher chances of getting sum >= k ) and then for larger and again larger so as to see if we can shrink ...
Am I Correct ?? IF NOT please correct sir 🙏🏻🙏🏻
Are aise samjho.
nums = {84, -37, 37, 40, 95}
cumSum = {84, 47, 84, 124, 219}
Let's say you are index j = 4, where cumSum is 219 >= k
Now, you want to shrink the window.
If you notice if you shrink and remove index 0 from left side i.e. 84
Then subarray sum from index 1 to index 4 will be = cumSum[j] - cumSum[0] = 219 - 84 = 135
But if you notice, even if you shrink the window further and remoce index 0 and index 1 from the window, you get the same answer= cumSum[j] - cumSum[2] = 219 - 84 = 135
So there was no point of keeping the first 84 because there was a dip from 84 to 47 and we can get sum >= k further also which will be even shorter subarray.
Hope this is clear
@gui-codes yaa bro got that thanks
Can't we keep count of negative no. We encounter in window if there is negative no. That means there is chance that sum would get increased hence we can shift the window towards left ..
[80 -30 50] k = 100 so how we can remove 80? it needs to be added in subarray then only we will be able to make 100? I didn't get that part
As soon as j reaches 50, the cumulativeSum[j] will become = 100
And if you notice I have put a check that if cumulativeSum[j] >= k
result = min(result, j+1)
So result becomes = 3
So we won’t miss that case also where we reach sum >= 100 here in this example
That was a good example. Thanks for this Qn ❤️🙏
Can we solved it using brute force?
yes, but it will only give TLE. But you must start with Brute force (82/98 testcase passed)
Java Brute force:
class Solution {
public int shortestSubarray(int[] nums, int k) {
int len = 10000000; //any max number
//check each subarray
for(int i = 0; i < nums.length; i++){
for(int j = i; j < nums.length; j++){
int sum = 0;
//window sum
for(int s = i; s = k){
len = Math.min(len, j - i + 1);
}
}
}
return len == 10000000 ? -1 : len;
}
}
Solved the medium after watching your video but stuck on this problem
😔😔
i was able to do the question you asked in the video but even after that aaj wala solution chamka nahi
sir please "sweep line " algorithm pe video banaiye..🥺🥺🥺🥺
Can we solve this question by not using dequeue?
Anyone need more clarity on why first 84 was removed from deque as soon as we saw a dip from 84 to 47. Here is more points to get more clarity.
nums = {84, -37, 37, 40, 95}
cumSum = {84, 47, 84, 124, 219}
Let's say you are index j = 4, where cumSum is 219 >= k
Now, you want to shrink the window.
If you notice if you shrink and remove index 0 from left side i.e. 84
Then subarray sum from index 1 to index 4 will be = cumSum[j] - cumSum[0] = 219 - 84 = 135
But if you notice, even if you shrink the window further and remoce index 0 and index 1 from the window, you get the same answer= cumSum[j] - cumSum[2] = 219 - 84 = 135
So there was no point of keeping the first 84 because there was a dip from 84 to 47 and we can get sum >= k further also which will be even shorter subarray.
Hope this is clear.
Thanks to MIK for improving my thinking skills.
my solution without using dq.
public int shortestSubarray(int[]nums,int k){
int n=nums.length;
long[]prefix =new long[n+1];
for(int i=0;i
Ist view as always ❤❤
Bhaiya mene bhi yehi example pe atak gya tha
bhaiya please use dark theme in vs code😅😅
Yes definitely. Actually i was travelling back home and hence forgot to switch to dark mode in rush. ❤️🙏
@@codestorywithMIKthanks 😀 also please make video on infix to postfix and prefix conversion using stack
First 🎉❤
(1574. Shortest Subarray to be Removed to Make Array Sorted ) bhaiya please isa monotonic sa bna do ma 3 din sa try kar ra 🙂🙂
First comment
sir black screen pe code kia kr ye pls ! anyways ,thanks for valuable effort
Sure definitely. ❤️
Next video in black screen
Why using Dequeue cant we use Stack here?As we can get increasing Sequence using Stack..What is the special advantage of using Double ended Queue ?it only allows insertion and deletion from both start and end
The only benefit is that you can shrink the window from left side which is the requirement of this problem. You can pop from left side and push from right side.
@gui-codes Yeah got it thanks..Saw his previous video on power subarrays part 1
bhaiya why 84 is irrelevant i didnt understand that part
Are aise samjho.
nums = {84, -37, 37, 40, 95}
cumSum = {84, 47, 84, 124, 219}
Let's say you are index j = 4, where cumSum is 219 >= k
Now, you want to shrink the window.
If you notice if you shrink and remove index 0 from left side i.e. 84
Then subarray sum from index 1 to index 4 will be = cumSum[j] - cumSum[0] = 219 - 84 = 135
But if you notice, even if you shrink the window further and remoce index 0 and index 1 from the window, you get the same answer= cumSum[j] - cumSum[2] = 219 - 84 = 135
So there was no point of keeping the first 84 because there was a dip from 84 to 47 and we can get sum >= k further also which will be even shorter subarray.
Hope this is clear
majo me bhai ?
sir leetcode ko dark mode kara karo plz
Yes actually i was travelling back to home. In rush i missed to make dark theme.
Apologies for inconvenience. Will take care from next video ❤️🙏
bhai java me code chahiye tha
Please check the github link in the description . It has java code too ❤️
why use deque why not just queue ?
In que you won’t be able to pop from behind to maintain monotonic nature. Notice that in order to make it increasingly monotonic we will have to pop from behind.
Also to shrink the window, we need to pop from front also. So deque provides both functionalites
late ho gaya thoda
Apologies for inconvenience.
I am exploring Hyderabad this long weekend and hence the delay. ❤️🙏
@@codestorywithMIK Dont even be sorry about it. I started solving daily challenges because of you posting the solutions later.