Minimum Size Subarray Sum | Leetcode #209

This video explains the minimum size subarray sum problem which is a variable size sliding window technique-based frequent interview problem. In this problem, I have explained the problem statement using easy-to-understand examples. I have explained the intuition for the algorithm using graph diagrams and then followed it up by a dry run and code explanation.

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=============================
==============================================================================

=======================================================================
USEFUL LINKS:

RELATED LINKS:

[CostaKazistov]

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.

[KingBobXVI]

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];
}
}

[vivekkumaragrawal]

class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = nums.size(), ans = INT_MAX;
int sum = 0;
int left = 0, right = 0;
while(right<len){
sum+=nums[right];
while(sum>=target && left<=right){
sum-=nums[left];
ans = min(ans, right-left+1);
left++;
}
right++;
}
return ans==INT_MAX?0:ans;
}
};

[urrahman]

21:45 cant find the next video? have you uploaded it?

[mtex]

I am not very good in time complexity theory, 5:36 how its become 10^10 and why should we go under <=10^8

[saivardhanpallerla]

Hi sir which app do u use for explaining

[nirajgujarathi]

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

[PraveshGupta]

Just curious to know, would it work for [7, 7, 8, 8] and target is 2 ?

[vinayghadigaonkar]

Are you Still Teaching the DSA CRASH COURSE?

[Kal_be_kal]

i didnt understand what ur algorithm is

[VinothOfficialClub]

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..

[pijushbiswas]

Could you help me understand, why won't this code work ?

int minSubArrayLen(int target, vector<int>& nums) {
long long int s=0;
int n=nums.size();
for(int i=0;i<n;i++) s+=nums[i];
if(s<target) return 0;
int l=0, r=n-1;
int sol=n;
while(l<=r) {
if(nums[l]<=nums[r]){
if(s-nums[l]>=target) {
s=s-nums[l];
l+=1;
} else break;
}else {
if(s-nums[r]>=target) {
s=s-nums[r];
r-=1;
} else break;
}
sol=min(sol, r-l+1);
}
return sol;
}

[devbhattacharya]

Sir one suggestion this video could be much shorter about of 15 mins although a great explanation thank you :)