The array contains non-negative numbers, only. with negative numbers the presented solution won't work. e.g. find the sub-array with sum greater than 50 in {-100, -200, -300, -400, -500, 50, 1, 2}
@@suvambasak9313 What was the issue you found with this input? I can see it won't work if the negative numbers are there. But what is the issue with the input you mentioned?
there is a slight code issue in second approach. Try this code instead var minSubArrayLen = function(target, nums) { let start=0,end=0, sum=0, minLength=Number.MAX_VALUE; while(end
In first program O(N^2): Add following line after 'if' condition in inner loop. This breaks and return loop if even after adding all elements, the sum is not greater than x: if ((end-start+1) == n && curr_sum < x) return 0; // No SubArray possible
the external for loop isnt making any sense if you have that and condition in the next while itself, moreover it isnt explicitly changing any variable on its own
in your first simple solution, you will never return min_len! you will always return 1! check the second loop, once you have curr_sum > x , it will go to first loop and it will return 1 since your "return min_len" is out of both loop
To handle negative numbers, add a condition to ignore subarrays with negative sums. You can find the complete code on the article: www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/
@@GeeksforGeeksVideos That implementation does not work either. Consider the array {10, -5, -4, 50, 51, -50, 20, 20} and x=100. The condition you add is never triggered and {50, 51} is never tested.
Yes, it's O(2n) ie O(n). Start and end pointer will traverse entire array in worst case. But those are not nested loops, those are independent loops. So n+n.
Because they haven't updated start yet when the min length is calculated. If start was incremented, then you'd need to add 1. Also, end is one index to the right of the actual end item that was added to sum, see the [end++] part. So no need to add + 1.
Thumbs down. Sorry. It's wrong. The author fails to consider the case where the array has negative numbers. And I don't think it can be solved in O(n). The answer is misleading.
The array contains non-negative numbers, only.
with negative numbers the presented solution won't work.
e.g. find the sub-array with sum greater than 50 in {-100, -200, -300, -400, -500, 50, 1, 2}
wont work for this also : arr = [1, 2, 3,4,1,2,10] value = 5
@@suvambasak9313 What was the issue you found with this input? I can see it won't work if the negative numbers are there. But what is the issue with the input you mentioned?
@@suvambasak9313 your implementation is wrong, it should work with this input.
@@suvambasak9313
for positive values :
int smallestSubWithSum(vector nums,int X){
int sum=0;
int start=0;
int end=0;
int mini=nums.size();
while(end
Try this for negative values :
int smallestSubWithSum(vector nums,int X){
int sum=0;
int start=0;
int end=0;
int mini=nums.size();
while(end
Fun fact: this code is not getting accepted by gfg,shows wrong answer for a particular case
Dont follow gfg
Try this condition along with this code if (n==1 && x==1 )return 0;
there is a slight code issue in second approach. Try this code instead
var minSubArrayLen = function(target, nums) {
let start=0,end=0, sum=0, minLength=Number.MAX_VALUE;
while(end
can this be solved using DP?
In first program O(N^2): Add following line after 'if' condition in inner loop. This breaks and return loop if even after adding all elements, the sum is not greater than x:
if ((end-start+1) == n && curr_sum < x) return 0; // No SubArray possible
the external for loop isnt making any sense if you have that and condition in the next while itself, moreover it isnt explicitly changing any variable on its own
in the first example why isn't {45,19} the smallest subarray
Hi Harsha,
{45,19} is not a subarray but a subsequence. {4, 45, 6} is a subarray as the elements are contiguous.
Please improve the volume of the video. I can hardly hear anything without using headphone
Why are we initailizing min_length as n+1. Even if we initialize it as n, it doesn't make any change to the output, can you please explain.
hey! can u explain y?
I mean min_length as n+1, but y?
@@adhvaithanayak1606 you can take min_len=n because all the sum of array is always greater than the given number
in your first simple solution, you will never return min_len! you will always return 1! check the second loop, once you have curr_sum > x , it will go to first loop and it will return 1 since your "return min_len" is out of both loop
How to return the subset, not the length of subset?
it is just for positive numbers in array i guess
To handle negative numbers, add a condition to ignore subarrays with negative sums.
You can find the complete code on the article: www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/
@@GeeksforGeeksVideos That implementation does not work either. Consider the array {10, -5, -4, 50, 51, -50, 20, 20} and x=100. The condition you add is never triggered and {50, 51} is never tested.
@@GeeksforGeeksVideos Input
[84,-37,32,40,95]
, X=167
Output:
5
Expected
: 3
It doesn't work with negative condition provided.
Why inner loop checks start < n? Wouldn't it be more logical while start < end (as it can not be higher)?
yes, the invariant should be start
Thanks, man, this video is very useful!
We're glad you found it useful. :)
this is not working for {-28,81,-20,28,-29} k = 89
very helpful
is the 2nd algorithm O (n) ?
Yes, it's O(2n) ie O(n). Start and end pointer will traverse entire array in worst case. But those are not nested loops, those are independent loops. So n+n.
revunuru satish how is O (2n)=O (n)?
Big O notation. Limit n->infinity 2n=n. Eg. n^2+4n+1~=n^2 for larger values of n. so O(n^2+4n+1) = O(n^2).
That Optimization was certainly a Ninja Trick!
Haha :D
perfect
Why is the array length end-start instead of end-start+1?
Because they haven't updated start yet when the min length is calculated. If start was incremented, then you'd need to add 1. Also, end is one index to the right of the actual end item that was added to sum, see the [end++] part. So no need to add + 1.
Solution in pythpn
I love you
wrong solution does not work
Try this condition along with this code if (n==1 && x==1 )return 0; thank me later
Thumbs down. Sorry. It's wrong. The author fails to consider the case where the array has negative numbers. And I don't think it can be solved in O(n). The answer is misleading.
Can't we use binary search on answer concept to guess the size of subarray and then ...