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
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 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
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
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
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;
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
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
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
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 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.
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
Please improve the volume of the video. I can hardly hear anything without using headphone
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.
How to return the subset, not the length of subset?
this is not working for {-28,81,-20,28,-29} k = 89
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).
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
wrong solution does not work
That Optimization was certainly a Ninja Trick!
Haha :D
Thanks, man, this video is very useful!
We're glad you found it useful. :)
Try this condition along with this code if (n==1 && x==1 )return 0; thank me later
very helpful
perfect
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 ...
I love you