10^5 size for N^2 problem becomes 10^10 - very interesting observation you noted. I never realised that about computation limits, such as 10^8 you mentioned. Learned something new today. Great walkthrough of Leetcode 209 btw. Clear and on point.
Excellent explanation of the problem overall, I kind of feel like the explanation of the +2 and inclusion of a second loop make it a little more confusing though, since a lot of time is spent explaining why it's +2 but that's a design choice rather than a necessary part of the overall algorithm. Time complexity is the same, but I feel like it's a little more straightforward (if more lengthy) like this: sum = nums[0]; while (true) { int sub_array_size = right - left + 1; if (sum >= target) { if (sub_array_size == 1) return 1; // In the case where nums[i] >= target, you know the answer is the minimum. Early out prevents the left index going to the right of the right index. shortest = min(sub_array_size, shortest); sum -= nums[left]; ++left; if (left == n) break; } else { ++right; if (right == n) break; sum += nums[right]; } }
class Solution { public: int minSubArrayLen(int target, vector& nums) { int len = nums.size(), ans = INT_MAX; int sum = 0; int left = 0,right = 0; while(right=target && left
found one modification, Correct me if I am wrong ! when , sum==target then no need to move left pointer because any ways it will lower the sum, In short if sum> target move left pointer towards right else if sum == taget update window size if it is smaller else if sum< target move right pointer
With the way his logic is written, it just keeps the code consistent - since the "left" pointer is always over-shooting by one, so that once the sub-array is too small, he'll include the sub-array plus the previous element, so if the sub array is currently [1, 2, 4], he wants to iterate again to 1, [2, 4] because now he'll count the length of the sub array (2) and add 1 extra to account for the over-shoot. I think the way he did that actually complicates the verbal explanation significantly, for the sake of the video. Doing it with two loops is unnecessary, as you could just do a single loop along the lines of: while (not finished) { int sub_array_size = right - left + 1; if (total >= target) { minimum_sub_array_size = min(sub_array_size, minimum_sub_array_size); ++left; } else { ++right; } }
For input target =7 and the array = {4,2,2,2,1,3}. how the solution find the correct answer based on your fix? the right pointer will reach end of an array and will tell the solution as 4.. not 2..
Order is N^2 & max input size will be 10^5, so 2*5 = 10, therefore 10^10. 10^8, here 8/2 = 4, all inputs till 10^4 can be solved with it. Which means, if we go under 10^8, we can solve for further higher input size. I hope, this helps.
Could you help me understand, why won't this code work ? int minSubArrayLen(int target, vector& nums) { long long int s=0; int n=nums.size(); for(int i=0;i
10^5 size for N^2 problem becomes 10^10 - very interesting observation you noted.
I never realised that about computation limits, such as 10^8 you mentioned.
Learned something new today.
Great walkthrough of Leetcode 209 btw. Clear and on point.
Are you working as a SDE?
😀
@@leetcoder1159 Currently, no - but preparing for future interviews. Doing 4-5 Leetcode medium every day (434 so far).
@@CostaKazistov great sir
@@CostaKazistov now?
Excellent explanation of the problem overall, I kind of feel like the explanation of the +2 and inclusion of a second loop make it a little more confusing though, since a lot of time is spent explaining why it's +2 but that's a design choice rather than a necessary part of the overall algorithm. Time complexity is the same, but I feel like it's a little more straightforward (if more lengthy) like this:
sum = nums[0];
while (true) {
int sub_array_size = right - left + 1;
if (sum >= target) {
if (sub_array_size == 1) return 1; // In the case where nums[i] >= target, you know the answer is the minimum. Early out prevents the left index going to the right of the right index.
shortest = min(sub_array_size, shortest);
sum -= nums[left];
++left;
if (left == n) break;
} else {
++right;
if (right == n) break;
sum += nums[right];
}
}
class Solution {
public:
int minSubArrayLen(int target, vector& nums) {
int len = nums.size(), ans = INT_MAX;
int sum = 0;
int left = 0,right = 0;
while(right=target && left
found one modification, Correct me if I am wrong ! when , sum==target then no need to move left pointer because any ways it will lower the sum,
In short if sum> target move left pointer towards right
else if sum == taget update window size if it is smaller
else if sum< target move right pointer
With the way his logic is written, it just keeps the code consistent - since the "left" pointer is always over-shooting by one, so that once the sub-array is too small, he'll include the sub-array plus the previous element, so if the sub array is currently [1, 2, 4], he wants to iterate again to 1, [2, 4] because now he'll count the length of the sub array (2) and add 1 extra to account for the over-shoot.
I think the way he did that actually complicates the verbal explanation significantly, for the sake of the video. Doing it with two loops is unnecessary, as you could just do a single loop along the lines of:
while (not finished) {
int sub_array_size = right - left + 1;
if (total >= target) {
minimum_sub_array_size = min(sub_array_size, minimum_sub_array_size);
++left;
} else {
++right;
}
}
thanksssss a lot ............awesome explanation
The best explanation Sensei
Thanks 😊
Well explained 🔥
Thanks 😊
very nice explanation
Thanks :)
Happy new year for you sir
Same to you 😀
For input target =7 and the array = {4,2,2,2,1,3}. how the solution find the correct answer based on your fix? the right pointer will reach end of an array and will tell the solution as 4.. not 2..
I am not very good in time complexity theory, 5:36 how its become 10^10 and why should we go under
Order is N^2 & max input size will be 10^5, so 2*5 = 10, therefore 10^10. 10^8, here 8/2 = 4, all inputs till 10^4 can be solved with it. Which means, if we go under 10^8, we can solve for further higher input size. I hope, this helps.
Hi sir which app do u use for explaining
One note
Are you Still Teaching the DSA CRASH COURSE?
Just curious to know , would it work for [7, 7, 8, 8] and target is 2 ?
Yes. r-l+2 = 0-1+2 = 1 :)
21:45 cant find the next video? have you uploaded it?
yes
Please search it if not linked.
Will add the link for it in description
i didnt understand what ur algorithm is
Sir one suggestion this video could be much shorter about of 15 mins although a great explanation thank you :)
Could you help me understand, why won't this code work ?
int minSubArrayLen(int target, vector& nums) {
long long int s=0;
int n=nums.size();
for(int i=0;i
fee of course??
Sir your Instagram link not working
Need to check it :)
Instagram Id plz sir