Subarray with given sum

[@techdose4u]

🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone] 🔴 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/

[@CodeSuccessChronicle]

your brain deserves more likes 👏

[@techdose4u]

😅

[@mikasaackerman2694]

Nice explanation. Isn't it the same question as subarray sum equals k. You have uploaded that video too and that works for every edge case as well as negative numbers.

[@techdose4u]

Thanks

[@mohit7717]

Thanks for sharing such a valuable programming content

[@madhz007]

Your explanation deserves more views

[@sujitgoswami4583]

NOTE:- I'd recommend you guys to know the logic and then write a simple JAVA,C/C++ code, vector isn't much required. those who are unable to solve it with vector, here's the full solution. :) JAVA:- static void subarraySum(int n, int s, int[] arr) { int start=0,end=0,sum=0, r=0; int i=0; while(is)//if sum becomes greater { start=start+1; sum=0; i=start-1; } if(sum==s)//if we found all index { r++; end=i+1; start++; break; } i++; } if(r>0) System.out.print(start+" "+end); else System.out.print("-1"); } -------------------------------------------------------------------- C++, #include vector subarraySum(int arr[], int n, int s){ int l = 0; int r = 0; int count = 0; vector res; while (r

[@techzone0131]

Bro gfg me ouput wrong bta rha h

[@padiakhil7620]

@@techzone0131 lol same, but we need to add another if block if given sum==0 thn return -1

[@wiccanmarvelous]

@@padiakhil7620 yes after this condition solution is perfect 😄

[@sravan.t7581]

why not in python?

[@Flux-e4y]

we cannot return -1 because it is a vector@@padiakhil7620

[@braj_marg]

thank you so much sir simple and easy explaination! radhavallabh shri harivansh

[@K_EC_AushoRoup]

What if there is more than one subarray whose sum is equal to the target sum. Then how will you modify your code? For reference see LeetCode 1171 problem. I know this 1171 LeetCode can be solved by another approach(I used Stack for solving it). But I want to apply Target sum subarray algorithm here in this question.

[@supriyamanna715]

then u use a hashmap to store the sums for each windows

[@shirish2005]

Nice explaination

[@sushobhitjakhmolaAdmin]

Hey what if after 10 there is 5. So when we get currentsum as 38 , adding next element -5 would make it as 33. Perhaps it isn't suitable for arrays containing negatives

[@tusharnain6652]

yes!

[@lazzyboii2573]

Then to use this algorithm maybe add all the elements with the most negative number so every element will be positive

[@Y_AnSHumaan]

You'll have to use an array with running/prefix sum to solve if the arrays also contains negatives.

[@motivation8238]

yes it will work only for positive numbers, if you want to handle negatives then you have to use hashmap

[@SurajKumar-cg1mm]

halo bro what will we do if our first element is greater then sum { 43, 1, 17, 26, 15 } and sum is 32

[@anuj4200]

If first element is greater then increment both right and left pointers.

[@techdose4u]

If you find either right or left element is greater then just skip over that element.

[@aryankhandelwal15]

@@techdose4u sir u should have mention this.

[@tejasdonadkar9094]

Please Explain Longest subarray with given sum using HashSet if possible

[@jawwadakhter5261]

really .........great explanation,u should keep on uploading like these content.

[@techdose4u]

Thanks :)

[@ankitchawla8487]

This was a good explanation thanks a lot for making this video.

[@senthilmurugan7304]

how to find all possible sub array consider [2,3,5,7,10,15] sum=10 here 7,3 one subset and 2,3,5 also another subset.

[@prashantprajul9526]

7and 3 is not a subarray

[@arijitchandra8218]

is it an implementation of sliding window technique?

[@techdose4u]

Yea

[@suyashmisra7406]

Hello friend,you're doing a great job and I am very thankful for these videos. I had a small doubt regarding your explanation of the time complexity. You said that since we're" passing" through each element a max of two times,the complexity should be O(2*N) which obviously is O(N). I think ,since incrementing left is an O(1) operation, it doesn't cause the time complexity to be O(2*N).It should still be O(N),simply because the loop will run for a max of n times(doing O(1) work each time) . Even though we get the same complexity eventually, getting the analysis wrong might be disastrous in an otherwise highly effective answer.

[@jaishreesaraswat2800]

Even I had the same doubt , did you find its solution?

[@phushyamithragauri9258]

I guess the loop ends when left and right == n ?? then there is chance of moving twice hence O(2*N).

[@San2shsingh]

Can you help me with python script for this

[@AgarwalAashi]

Very nicely explained!

[@techdose4u]

Thanks :)

[@sigma7253]

@@techdose4u what if its starts with -ve array

[@abdurrehmanansari9219]

Copy hai code from geeks for geek site and even variable is same..

[@Kushagra_21]

sir your videos has helped a lot . Sir can you tell me from where should i prepare for technical mcqs . I have exam of accolite company next week. Thankyou for the help.

[@techdose4u]

Well for short time, if you have GATE notes then revise DBMS and OS atleast, otherwise, just study important MCQ questions from geeks and search for top 50 and top100 MCQ questions for interviews. That should help :)

[@Kushagra_21]

@@techdose4u thanks a lot sir

[@techdose4u]

Welcome :)

[@gaurika4927]

What is negative elements are also present [4,-1,-2,0,3,1] and sum 1

[@memeologicalworld8929]

But when we need to go upto n-1 then at n-1 we have our sum equal to required sum but loop again run and i=n so,loop ends and there are more problems on this when you are going to submit on gfg,leetcode,etc.🧐

[@arpanbarua5424]

Plz type the code aslo❤❤either way nice and good video🎉🎉

[@aasifali9139]

thx brother it was really helpful....

[@for461]

[1,1,2] --> will fail ? for target 2 should return position 2.

[@shubrochakroborty5918]

Bro you are just awesome

[@techdose4u]

Thanks :)

[@jordan_heartz]

Input nums = [-1,-1,1] k = 0 Use Testcase Output 0 Expected 1 ### This approach will not work for negative numbers

[@hmmmsmmsmsmsm]

I came here after code chef long competition find lowest sub array with sum k 😶

[@057anmolkesarwani4]

Nice one

[@techdose4u]

Thanks

[@GdLongerHandle]

what if sum = 15. right pointer will stop at 2. And till 2 we shall not have any subarray with sum =15

[@mayurkoli4145]

approach not work on array having negative numbers arr : [-1, -1, 1] target = 0, Not a generalize solution.

[@techdose4u]

I have already answered on your comment 6 months back. Please search it in comment section. You asked the same question.

[@mayurkoli4145]

​@@techdose4u ohh sry!!!! : )

[@techdose4u]

No problem :)

[@msahai7017]

Hi...How can we do the same thing using maps??

[@askchaitanya97]

What of there is 9 at index 4 and sum is still 33? I mean what if we have subarray sums greater than or lower than the given sum , but not exactly equal to it?

[@edenfire1221]

Yeah, either we are looking for something else, or this is wrong.. if its 9 at index 4, it wont know the sum of index 0, 2, 3, and 4 = 33.

[@LightningXThunderVlogs]

vector subarraySum(int arr[], int n, int s) // NOTE : array contains non-negative integers { if(s == 0){ // handle sum = 0 for(int i=0; i

[@mrsmurf911]

small modification for GFG Practice: return vector{l+1,r}; instead of return vector{l,r-1};

[@chrisogonas]

Very well explained! Thanks

[@siddharthashankar8396]

Very Helpful

[@vithleshkumargupta]

you are doing great work👍👍

[@techdose4u]

Thanks :)

[@karanalang1573]

nice explanation .. can you pls provide sample code ?

[@techdose4u]

Will try to.

[@gopikamurali440]

Pls give code

[@selectivitism]

This solution is so damn freaking clever!

[@techdose4u]

:)

[@ecstacist6749]

Thank you ! What if the solution elements are non_consequtive

[@PankajSingh-mm3br]

A subarray is a contiguous part of array. An array that is inside another array

[@cuteminired6550]

​@@PankajSingh-mm3br thanks

[@Usurperhk]

What if the left pointer become equal to or exceeds the right pointer??? FIX IT!!!!

[@TechDextro]

what if there are negative elements in the array

[@howardlam6181]

what if the subarray does not need to be consecutive numbers. There can be "holes" in the middle. That's you get the minimum number of elements from the array to reach the sum.

[@Spark_T_ai]

subarray by definition means contiguous ,, i guess that should be in the description

[@howardlam6181]

@@Spark_T_ai yea it's actually subsequence in that case. It was for a different problem but I figured out the solution anyway.

[@c56tejashsharan37]

it will not work if there will be negative numbers in the subarray

[@kashifanwar9733]

nice approach

[@techdose4u]

:)

[@varun8441]

what will be termination condition if we don't find and sum equal to given sum??

[@techdose4u]

Termination will be when right pointer goes out of bounds, that is, when right pointer goes beyond last value in array.

[@eeshgadol]

Code, java , this approach with one loop!: public static ArrayList subarraySum(int[] arr, int n, int s) { ArrayList result= new ArrayList(); int left=0; int right=0; int sum=arr[left]; while(rights) { sum=sum-arr[left]; //System.out.println("sum minus left " + sum); left++; } else if(sum

[@gauravborkar1345]

Excellent

[@vivekkumar-fk9lc]

But instead of giving the longest subarray, it will return the first subarray having sum equal to k.. How would we get the largest sum

[@hersheynohara5887]

Thanks for the video...

[@techdose4u]

Welcome :)

[@chetanpadhen7780]

Sir If You Also Go Through To The Code,It Will Be More Helpful. Thanks

[@techworld3043]

what software do you use to teach ?

[@this.supratim]

Great explanation 👌

[@techdose4u]

Thanks :)

[@inderjeetchawla527]

Bhai negative elements bhi ho array me to. And Bhai jab video banao to saare cases cover Kia Karo plz.

[@techdose4u]

Yes you are correct. I did not cover for negative numbers. You can do so by using the modified kadane's algorithm which works for negative numbers as well. Whenever you are given a negative number as sum then negate the sum to make it positive and also negate all the elements of the array and so sum to be found will always be positive and so you can use kadane's algorithm.

[@ayushkashyap8299]

I think finding all subsets of a array is O(2^n) not O(n^2). Correct me if I am wrong.

[@techdose4u]

There are 2^n possible subsets of an array. So yeah, you are correct. I might have mistakenly told something, my bad.

[@indyarockers]

all subsets of array is O(2^n) but consecutive subsets of an array is just O(n^2).

[@secularph8424]

That's for non continuous Subarray, For continuous Subarray its O(n^2)

[@AvinashJ21]

To move pointers we need while loop ?

[@mameabera5852]

what if the array is [17, 85, 93, -45, -21] and sum = 150 . this doesn't work by your algo

[@varun8441]

what will be termination condition if we dont find and sum equal to given sum??

[@srajsekhar4061]

Nice explanation 👌👌👌 bro

[@techdose4u]

Thanks bro :)

[@Nikita-hv5jm]

Can we use kdane's algo for this problem?

[@techdose4u]

Try 2 pointer technique.

[@shashikumari4000]

What if sum is 9 only 5 and 4 satisfies.... Can someone explain this🙏 how will the algorithm with

[@mandeepdas351]

the explanation is about finding subarray and not subsequence. 5 ,4 is not a subarray.

[@nabeelahahmed4610]

Can u share the entire code plz? That will be better to understand more properly

[@akshayzade9761]

static ArrayList subarraySum(int[] arr, int n, int s) { ArrayList list = new ArrayList(); int left = 0, right=0; int currentsum = arr[0]; try { for(int i=1; i s) { currentsum = currentsum - arr[left]; left +=1; } } else if(currentsum > s) { currentsum = currentsum - arr[left]; left += 1; } } } catch(ArrayIndexOutOfBoundsException e) { list.add(-1); } return list; } Sir might have better code structure solution has this. but mine is also working as per sir approach

[@aryankhandelwal15]

o bhai bhot hard lg rha tha

[@tarzanyt3047]

you are amazing

[@leetcoder6569]

Great

[@shrimatkapoor2200]

Also, this would only work for continuous sub-arrays would it not?

[@techdose4u]

Subarray is continuous only. If something is not continuous then it is either subsequence or subset. This will work only for subarrays.

[@shrimatkapoor2200]

@@techdose4u Cool I think I was looking for the solution for subsets and target sums. Thanks for the clarification.

[@snehill7275]

I am not sure if the TC is O(n) here, because in the worst case we have to move n-1 time backward on that moment TC will n x (n-1) => O(N^2) ex- [1,2,20,10,2], sum = 12 sum_will be like = 1,3,23 12) we go backward 23-1= 22 , 22-2= 20, 20-10=10 as 10 < 2 we can move forward and doing so we will ended up with answer => (3,4) pls, correct me if I am wrong.

[@Shanky_17]

CAN WE USE THE SAME METHOD IF THERE ARE MORE THAN ONE SUB-ARRAY WITH SUM =K ? and is it sliding window ?

[@parthanuj8611]

I think that would not be the case when u are solving porgram in leetcode or gfg but yeah it is possible ..

[@koushikshomchoudhury9108]

What you've shown is called a Sliding Window approach. Unfortunately it's an O(n^2) solution.

[@techdose4u]

You are mistaken. It's O(N) only. How did you conclude O(N^2) ?

[@sonusangwan7898]

great video brother

[@techdose4u]

Thanks :)

[@leetcodepythonsolutionsand9396]

Can you provide explanation of the DP solution?

[@surajsingh-sm7qx]

U r awesome

[@poonamsangale4037]

Sir you have explained very well but can you please provide us code

[@techdose4u]

I was not providing the code earlier but now I do.

[@shouryagupta8763]

nice sir

[@dev.suyash]

Sir,Can you please share code for this mentioned approach?

[@akshayzade9761]

static ArrayList subarraySum(int[] arr, int n, int s) { ArrayList list = new ArrayList(); int left = 0, right=0; int currentsum = arr[0]; try { for(int i=1; i s) { currentsum = currentsum - arr[left]; left +=1; } } else if(currentsum > s) { currentsum = currentsum - arr[left]; left += 1; } } } catch(ArrayIndexOutOfBoundsException e) { list.add(-1); } return list; }

[@vinayak186f3]

Will it work for array with some negative elements ? I think it won't , correct me if wrong

[@sigma7253]

what if we start arr[0] is -ve

[@shrimatkapoor2200]

Isn't the number of subsets of a finite set 2^n for n cardinality of the set

[@techdose4u]

You are correct. But here we are solving subarray which is continuous and not subset. So it will be N^2 for subarray.

[@rahu1119]

which presentation software is this ?

[@khushijain3574]

which software you are using

[@ajaygonepuri2285]

thank you sir!

[@atiquesiddiqui710]

Can you please provide the code for this

[@euphoric3464]

I don't think this will work for all kind of arrays like a={2,4,6,8,9,10}

[@tokirmanva2247]

This approach won't work if there are negative numbers also.

[@comradepb]

Two pointer approach is not good here because the array can have negative numbers.

[@sukdipkar8876]

yaa it is going well but it exceeded time limit.

[@ryan-bo2xi]

this uses dynamic window technique

[@techdose4u]

Yea :)

[@K_EC_AushoRoup]

Agreed

[@akshhay]

Ye contigious hogyi, what if we want any subarray?

[@theWrongCode]

we changed this problem with array containing multiple subarray with given sum.

[@prabhatkashyap8333]

did the same on geeksforgeeks platform, showing TLE.

[@techdose4u]

Should not give TLE bro :( Is there any algo to calculate below O(N) time?

[@prabhatkashyap8333]

@@techdose4u i think sliding window, thats what i am also looking for.

[@techdose4u]

@@prabhatkashyap8333 yes correct.

[@prabhatkashyap8333]

@@techdose4u ide.geeksforgeeks.org/iN2jy9gvuo check this, and try to submit it on GFG, practice.geeksforgeeks.org/problems/subarray-with-given-sum/0 and tell me the mistake, why TLE?

[@steevjames6720]

What if there are negative numbers ?

[@yaswanthreddy372]

thanks bro,its working

[@techdose4u]

Welcome :)

[@dayagutte45]

@@techdose4u plz give me solution of this Write a program to find lowest number of integers in the array that sums up the given number. In java,c,c++ only no python Write a program to find lowest number of integers in the array that sums up the given number. The program should ask user to input array of integers (“Input Array”) and the required sum (“Required Sum”). The output (“Output”) should list the lowest number of integers from the input array that sums up the “Required Sum”. Refer to examples given below. Input : Array of integers Required sum Output : Elements from array which makes sum equals to given value Example: Input Array : [10, 0, -1, 20, 25, 30] Required Sum: 45 Output: [20, 25] Required Sum: 59 Output: [10, -1, 20, 30] Required Sum: 60 Output: [10, 20, 30]

[@dayagutte45]

Can u provide a code plz

[@dayagutte45]

Can u provide a code plz

[@user-so9jd2nf4s]

Hey, how to find multiple sub arrays?

[@mahesan2881]

I don't think the second method is correct, what if the first element contains 10000. That is larger than the sum 33, but if r goes one step ahead, then the currsum will not decrease but increase.

[@eyasir2047]

Two pointer approach

[@pepetikesavasiddhardha7852]

simple yet sexy logic....

[@piyushverma5797]

find subarray with given sum negative numbers allowed in constant space

[@sunnyvarun6652]

How will this problem be solved? int arr[]= {1,4,45,6,10,8}, target=11.

[@satyamsingh_47]

This is a subset sum problem which is different from a subarray sum problem

[@techie_bhuvi]

This will fail for negative number [-1,-1,1] expected 1 but this code will return 0

[@akp_04]

wrong solution. your sol will only work in case when array is sorted. if there are negative numbers and array is not sorted this wont work. you should highlight the constraints in the beginning of the video. nonetheless explanation was good

[@neghatnazir1668]

hey i have a doubt regarding time complexity. e.g if we are given 1 2 5 10 ,sum=10 the second pointer is going to move till n, in this case the time complexity would b O(n^2). i am confused, can you please explain this case

[@supratikpadhee4235]

to understand tc , always find how many times the particular element is processed . In this case as @tech dose explained , in the worst case scenario , we shall need to process the element 2 times , so total complexity = O(2* n )

[@supratikpadhee4235]

as per your doubt , it will not be O(n^2) in the efficient approach ? why ? | | -----> window bounded by left and right pointers. | 1| , | 1 , 2| , | 1 , 2 ,5| , | 1 , 2 ,5 , 10| , | 2 ,5 , 10| , | 5 , 10| , | 10| ------> different states of the window in the worst case , our window can take 2n states , i.e increase and then decrease , so at max TC = O(2n).

[@neghatnazir1668]

@@supratikpadhee4235 thanks :)

[@neghatnazir1668]

@@supratikpadhee4235 thanks :) i checked it after

[@runtimeError123]

It will fail bro in many cases Example [-1, -1, 0] and k=0 . Here he have to count entire array also.