Sliding window with two pointer solution breaks down if you have negative numbers in the array. A more resilient approach is to add the sum as we go and put in a hashmap from sum to index of sum. So at index i, all we need to do is check if a complement sum exists i.e. (sumSoFar - Target) exists in the map and update if the value from the map map map[ i - index] is larger than max length. this is O(N), uses one pointer and works with negative entries
I worked my entire career (45 years) as a software engineer and I never, ever had to address a coding problem like this. Why in the world are these kinds of questions part of programmer interview questions?
Roger Garrett Hi Mr. Garett, I was 13 years old and started programming. I am 20 now and without a degree have got a job as full stack dev, whereas I feel like these problems can help me be a better thinker, they aswell make me aware of these kind of problems like time complexity and the bruteforce problem and the sliding window approach. Thats why I think these questions contribute to a programmer interview.
I see a few people saying the nested while loop makes the time complexity n^2. It does not, because the inner loop is not depending on the size of n. This algorithm is still linear.
@@NickWhite Yo I just started doing these coding challenges like a week ago and I've literally been cramming your channel because I have an interview with one of the FAANG companies next week. The only thing your channel does not go over in depth is recursion and dynamic programming. More videos on that would be awesome. 👏
@Emmanuel Onwumah I did not understand this. Say instead of 3 zeros, the array has 50 zeros, then won't the inner while loop will loop for 50 times, thereby not being linear? I get it won't loop for the length of the loop (being n) like the first loop but still the inner while loop in itself will be linear time and being inside another loop, it will make the time complexity of also n^2.
Parag Agrawal Ok so time complexity is only measured in reference to operation being performed * size of variable. In this case length of the array is the variable. The out while loop ONLY focus on the right pointer and the length. The inner while ONLY focuses on the left point and the sum. The inner loop is only invoked if that special case is met. It is not invoked on every iteration. Meaning if the rightpointer reaches arr.length the both loops will end regardless what is happening to the left pointer.
@@emmanuelonwumah915 Ohh! Got it. So its kinda inverse looping (from the norm of a brute force algo) where the outer loop is moving the right pointer and the inner loop is moving the left pointer. Got it. Thanks for explaining.
Not really. You add an additional operation EVERY iteration to remove a few operations on SOME iterations. There can be cases where it is an optimization, and other cases where it makes the program slower. Also both solutions are on the same order so it doesn't really matter.
@@elijahbuscho7715 But you will have FEWER iterations. The question here really is this: How often do we have to update the left pointer, and how often the right pointer? Well, the right pointer is N times, as we have to get to end of the array. The left pointer is what changes between the two proposals. Let L be the length of the largest sub array we want. If we update the left each we update the right, then we update the left about N - L times, as we stop updating the left once the right hits the end of the array. In the one where we have the left play catchup, we have to do at least N - L updates, as we could risk having to move the left pointer beoynd the N - L position. In short, we save some time, which could be quite a lot if the largest array is big and we have a few high values at the end.
@@09TYPER I thought the same but then I re read the question. It says look for a contiguous sub array, so that means you cant alter the order of the array given to you. So there is no problem with the sliding window on this problem, sorted or not. Hope this makes sense.
I might be mistaken, but instead of only incrementing your left pointer when current_sum is higher than s (while r != [-1]), could you not increment both pointers, because you don't care about any array that's shorter than your currently found subarray? (Of course, if you have not found a proper subarray (and r == [-1]), then you need to only increment the left pointer.) Of course, this would not reduce the solution to less than O(n), but would change it to worst case ~n instead of ~2n (if I'm not mistaken)
You can't increase both pointers running into problems (using 1-based index here): Imagine looking for sum=13 in [13, 1, 1, 1, 12] First hit is [1, 1] Next it will go through the loop until currentSum > sum at [2, 5] with a currentSum of 15. At this point increasing both pointers would both cause an error while also failing to produce the actual solution of [4, 5]
You can also add a contidion that exits the loop if the total length of the array subtracted by the current position is shorter than the length of the subarray we already found, because then we can't find any subarray longer then that already found.
Since the array is not sorted, you may have smaller numbers at the right end of the array which you can add to the sum and larger numbers towards the beginning of the array that you can subtract from the sum. In that case you would have added more numbers than you would subtract contributing to a longer subarray
A naive nested loop has worse efficiency than you might think. There are O(n^2) ranges calculate sums for. Calculating the sum of those ranges is not O(1), since the length of those ranges is proportional to n. Of course, you can trivially change the naive algorithm to O(n^2) by filling in every possible sum into a 2D array (i.e., by using dynamic programming). That said, the problem constraints guarantee that array members are always >= 0, so the sliding window approach is far superior.
Since the first 8 array elements sum to 15, you would then only need to check subarrays of length 9 or longer (starting at elements 2, 3, 4, and 5). Once you don't find any of length 9 and all of those length 9 sums are more than 15, you would be done.
Some people think that two nested while loops have time complexity O(n^2). pay attention to the explanation the pointers never go back to the start of the array they just move in one direction so linear time
9:02 is that really necessary? Why check the sum, when you already know the current subarray you're checking has less items than the subarray we found earlier, which is 8 items long? No way it will be the longest subarray. Shouldn't you move the yellow arrow instead?
You didn't have to freeze right pointer until you have current_sum equal to given sum (while moving left one further). You could just slide the window for 9 elements to the right until it's less or equal of the given sum. Your goal is to find a window with more than 8, so, why shrink it?
OH MY GOD! So I've been watching your videos and solving these questions for the past 4 hours. I could finally come up with the right solution this time. I'm not so rusty after all! So pumped rn! lol
I totally agree. Some of the problem description often make things look more complex than it should. I tend to read them like 3 times to make sure I understand it.
instead of storing result as as an array of left and right variables, we can just store the current maximum length of the subarray sum. Then if right - left is greater than result we update result as right-left.
how about sorting the array first, then start with the moving window and return the first found solution? since all the numbers next are bigger, so it cant become longer. worst case is worst here, but average should be (maybe) better?
Can we solve this problem by : 1. Sort array in ascending order 2. Add up the sum for each array element I think it also require O(n). So, can we solve the problem by this approach?
that wouldn't work. How do you determine the indices after the fact? What if there are repeated values - which one's which? Is your sort stable? But mostly you're completely changing the order of the values in the original array so you lose cohesion.
If you want another solution you could: 1.Create an array pref[i]=arr[i]+arr[i-1]+...arr[0] O(n) 2. So now if we want the sum of the segment arr[i...j] we can do pref[j]-pref[i]+arr[i] 3. We can try some binary search stuff for every i=0...n-1 which would take O(nlogn) So yeah his two pointers solution is much better.
At a real life coding interview, you can always ask the interviewer for clarification of the question if needed. Imagine this just simulating the clarification of the question.
if there were negative numbers in the array, this algorithm will not work, you have to use prefix sum. Because this algorithm is base on a rule that if you expand the right -> the sum will increase, if you shrink the left -> the sum will decrease. Unfortunately that's not the case for negative numbers.
Are negative numbers allowed in input array? I missed it, but I guess not allowed. Because I can make counterexample input like [a0, ..., aN, -sumOfThose + desiredSumOfSubarray]
Assuming I understand you correctly, then in that case, right would be equal to arr.length. And thus the answer must be yes, since you cannot create a longer array. Edit: Assuming r != [-1]
If arr=[1,2,3,7,5] and sum = 9 the longest sub array adding up to 9 is [1,3,5] this algorithm will not find it because it only works for contiguous subarrays and it would be beneficial to state so in the problem description in the beginning of the video.
I wee where you're coming from, but subarrays can only be continuous. [1,3,5] is not a subarray of [1,2,3,7,5]. Imagine a subarray like being a slice of the array.
@Nick White Thanks again for great explanation. Can you please answer just one more question I tried solving this question on my own before looking at this video on CodeSignal, I could solve it with single loop & sliding window however it couldn't cover the edge cases like *(new int[]{1, 0, 2, 0, 0, 0, 0, 0}, 0);*. I spent 2 hours figuring out a solution that'd work for both normal cases & edge cases, however I couldn't. The question is: Did you solve this question on your own, if so, how long did it take you to solve it? Second, if not, did you watch someone else's solution & than understand that solution to solve this problem? I feel like I'm not good enough since I couldn't solve it on my own & I had to look at other's solutions to figure out a solution. This is making feel worried if I'm good enough for the coding interviews at Big companies like Google, Facebook, Microsoft or Amazon.
How would you do this if instead of an array/list, it was a set, so find the longest set of numbers that add to the sum (where order doesn't matter)? Would you have to store every single set that doesn't add up to greater than S?
Porco-espinho Entediado you cannot do binary search since the array is not sorted. The prefix sum will not be sorted either because negatives will decrease the sum
I don't know if my solution is more efficient or not but still, here it is : Step 1: sort the array in ascending order Step 2: loop through the sorted array and keep adding the elements until the sum becomes equal to the given no. Step 3: Once the array sum becomes equal to the given number pick the positions and return them.
In addition to what Ankit said: sorting has a best case time complexity of O(n log n). So Nick's algorithm would return the correct answer before you even finish with your first step (since Nick's solution is O(n)). (Side note: not that I could do any better, either. I only managed to come up with a O(n^2) solution before seeing Nick's solution.)
I understood the optimal solution because you explained it clearly, but couldn't understand the brute force solution 5:33 (you just said "keep going, next one, look at all of em") pls explain brute force solutions clearly too.
Bruteforce solution: (If at any point the sum of a subarray is equal to s, you have the answer) - First check if the sum of the whole array (of length n) is equal to s. - Then check if any subarray of length n-1 is equal to s. - Then check for any sub array of n-2 ... - Continue until you've checked all subarrays of size 3, then 2, then 1.. - If you still haven't found a subarray with sum s, then there is none and you return [-1].
so Nick, there's one thing I'm not quite getting - you say that you hope people can nail problems like this and get a job. You're a Leetcoding monster yet - I believe - you haven't got an offer yet? Is it because even rehearsing all the Leetcode, Facebook, Google, Amazon, blah blah questions in the world won't help in a live tech interview, or is there something else (the hemp debacle at Google notwithstanding)? It seems to me that on the basis of answering coding questions you should definitely be hired. It's a bit worrying if that's not the case. What does it take?!?!? Does this also mean that all these coding sites that are popping up from various youtubers are selling snakeoil if it makes no difference, regardless of the reams of testimonials they supposedly have (I'm very doubtful: at least one of those guys is a known BS artist). Thanks and good luck!
I currently have a job and also have had plenty of positions in the past please watch my video from save a lot to $55 / hour or you can see my LinkedIn in description
@@NickWhite OK, sorry: I mustn't have watched enough vids yet. I obviously came to the conclusion that you have been interviewing but no-one has seen fit to extend an offer. You're obviously a talented engineer so it'd be worrying if even someone with such a track record of solving problems is not getting offers. I hope you continue with the channel. Much respect for you and your many talents (not least the songs :D)
Didn't realize this would work as long as it's positive. I thought this approach only works if you sorted the array... So if negatives were involved, prefix sum is the answer?
Hi Nick..nice job... But one important question... Doesn't this approach looks like the elements in the array should be sorted...as you are popping out the LHS elements on the sum being greater than S??
I thought the same thing. I didn't think it would work on an array like [0, 0, ... numbers, 0] since it would likely pop off the initial 0s at some point. But then I thought about what a sub array really means, and its likely the problem doesnt allow you to pick numbers that arent adjacent. Like if you did a slice on the array.
I have got a question. I think your first example was wrong. Index of 2 was 1 in your array. I don't know Java's indexing rules but it's wrong in python. And, I want to publish my python answer: def findLongestSubarrayBySum(arr, s):# O(n^2) O(1) r = [] for i in range(len(arr)): for j in range(i, len(arr)): if sum(arr[i:j]) == s and len(arr[i:j]) > len(r): r = [i, j] return r
Find the maximum number after adding n number of comma example 455 and count of comma is. 1 then 4,55 so maxnumber is 55 can you find suitable solution of it
I don't understand, I feel there are use cases where this wouldn't work. For example (looking for a sum of 15) [5, 11, 10] The window wouldn't see any arrays that add up to 15. Edit: I see now that it's consecutive elements.
this is better int[] result = new int[], {-1,-1}; int left =0; int sum = arr[left]; int right = 0; while(right < arr.length) { sum +=arr[right]; if(sum == s) { result = new int[] {left,right}; right++ } else if(sum>s) { if(right-left>result[1]-result[0]) { sum-=arr[left++]; } else { right++; } } return result;
Cant we move both the left and right pointers together?! after all the window was longest :/ so just moving the left slider is only gonna make it small which is not a desired result anyways
The left and right pointer will both only move to the right. They can thus only move O(n) times, and since the rest of the algorithm is constant time for each configuration of pointers, the algorithm is O(n)
Hi! What will happen if I try to go from the begin and the end of the array, moving borders to each other while sum inside is not equal to the value (comparing arr[left] and arr[right] and deleting from subarray the biggest)? I'm feeling something will go wrong, but can't catch what.
your approach seems O(n^2) to me but can you explain how will to add the elements in a variable if your first pointer is at the start I mean which pointer you are using for adding and which for subtracting the values from sum
This solution, seems to fail for this kind of case: arr = a = [-2, -3, 4, -1, -2, 1, 5, -3] s = 6 given the constraints where we are guaranteed only positives. If that were removed, is it possible to tweak this to result in a correct solution too?
Your case as no solution, but this code will tell you : function findLongestSubarrayBySum (arr, s) { var len = arr.length; var deb = 0, fin = 0, sum = 0; var r = [-1], ln = 0; while (deb < len) { for (; sum ln) { ln = fin-deb; r = [(deb+1),fin]; } } for (; (sum > s || fin >= len) && deb < fin ;) { sum -= arr[deb]; deb += 1; if (sum === s && fin-deb > ln) { ln = fin-deb; r = [(deb+1),fin]; } } } return r; }
If right is as the end, you can return if the current window size is < the size of the current result or if the window sum is > the target sum. In those cases, you already know that further sums can't satisfy the condition.
Thank you for the explanation Nick. Can you think about starting a Ds Algo Series from scratch, so that beginners like me can learn from a great teacher like you?
I can recommend the videos done by Robert Sedgewick. If you want additional reading that matches the videos, they follow the structure of the book co-authored by Sedgewick himself.
Hey nick, great video. One thing is that I really think that in addition to your explanation of the problem, you should add the formal question on the side. In this particular problem you didn't mention the fact that the array has to be non negative which is crucial for the linear solution.
Sliding window with two pointer solution breaks down if you have negative numbers in the array.
A more resilient approach is to add the sum as we go and put in a hashmap from sum to index of sum.
So at index i, all we need to do is check if a complement sum exists i.e. (sumSoFar - Target) exists in the map and update if the value from the map map map[ i - index] is larger than max length. this is O(N), uses one pointer and works with negative entries
I worked my entire career (45 years) as a software engineer and I never, ever had to address a coding problem like this. Why in the world are these kinds of questions part of programmer interview questions?
It teaches us newcomers how to think
It makes sure you know how to develop an algorithm and how to make sure you don't wreck your big O
Roger Garrett Hi Mr. Garett, I was 13 years old and started programming. I am 20 now and without a degree have got a job as full stack dev, whereas I feel like these problems can help me be a better thinker, they aswell make me aware of these kind of problems like time complexity and the bruteforce problem and the sliding window approach. Thats why I think these questions contribute to a programmer interview.
It's because software engineer jobs pay 6 figures out of college so everyone started trying it. Now they need a way to weed out people.
I agree with you on this particular question but a lot of the questions that i see are pretty relevant this is shit
I see a few people saying the nested while loop makes the time complexity n^2. It does not, because the inner loop is not depending on the size of n. This algorithm is still linear.
s/o to you my guy
@@NickWhite Yo I just started doing these coding challenges like a week ago and I've literally been cramming your channel because I have an interview with one of the FAANG companies next week. The only thing your channel does not go over in depth is recursion and dynamic programming. More videos on that would be awesome. 👏
@Emmanuel Onwumah I did not understand this. Say instead of 3 zeros, the array has 50 zeros, then won't the inner while loop will loop for 50 times, thereby not being linear? I get it won't loop for the length of the loop (being n) like the first loop but still the inner while loop in itself will be linear time and being inside another loop, it will make the time complexity of also n^2.
Parag Agrawal Ok so time complexity is only measured in reference to operation being performed * size of variable. In this case length of the array is the variable. The out while loop ONLY focus on the right pointer and the length. The inner while ONLY focuses on the left point and the sum. The inner loop is only invoked if that special case is met. It is not invoked on every iteration. Meaning if the rightpointer reaches arr.length the both loops will end regardless what is happening to the left pointer.
@@emmanuelonwumah915 Ohh! Got it. So its kinda inverse looping (from the norm of a brute force algo) where the outer loop is moving the right pointer and the inner loop is moving the left pointer. Got it. Thanks for explaining.
Can be optimised further by keeping the window size to at least the size of last found window
Not really. You add an additional operation EVERY iteration to remove a few operations on SOME iterations. There can be cases where it is an optimization, and other cases where it makes the program slower. Also both solutions are on the same order so it doesn't really matter.
@@elijahbuscho7715 But you will have FEWER iterations.
The question here really is this: How often do we have to update the left pointer, and how often the right pointer? Well, the right pointer is N times, as we have to get to end of the array.
The left pointer is what changes between the two proposals. Let L be the length of the largest sub array we want. If we update the left each we update the right, then we update the left about N - L times, as we stop updating the left once the right hits the end of the array.
In the one where we have the left play catchup, we have to do at least N - L updates, as we could risk having to move the left pointer beoynd the N - L position.
In short, we save some time, which could be quite a lot if the largest array is big and we have a few high values at the end.
One important thing to know is that this approach works as long as there are no negatives. (2 pointers usually don't work when there's negatives)
And sorted.
@@09TYPER I thought the same but then I re read the question. It says look for a contiguous sub array, so that means you cant alter the order of the array given to you. So there is no problem with the sliding window on this problem, sorted or not. Hope this makes sense.
@@Will-en6gw but if it is not sorted, whats the point of two pointer and do left++ and right-- ?
This is exactly how I thought I would solve it but didn't know it has a name "slicing window approach".
Sliding*
I heard these words and techniques only after coming to USA ...
You're a natural programmer then
Nick I had an interview on super short notice and all I did was watch your videos. You were CLUTCH! Aced them. Thanks a lot for the content :)
I might be mistaken, but instead of only incrementing your left pointer when current_sum is higher than s (while r != [-1]), could you not increment both pointers, because you don't care about any array that's shorter than your currently found subarray? (Of course, if you have not found a proper subarray (and r == [-1]), then you need to only increment the left pointer.)
Of course, this would not reduce the solution to less than O(n), but would change it to worst case ~n instead of ~2n (if I'm not mistaken)
You can't increase both pointers running into problems (using 1-based index here):
Imagine looking for sum=13 in [13, 1, 1, 1, 12]
First hit is [1, 1]
Next it will go through the loop until currentSum > sum at [2, 5] with a currentSum of 15.
At this point increasing both pointers would both cause an error while also failing to produce the actual solution of [4, 5]
You can also add a contidion that exits the loop if the total length of the array subtracted by the current position is shorter than the length of the subarray we already found, because then we can't find any subarray longer then that already found.
Since the array is not sorted, you may have smaller numbers at the right end of the array which you can add to the sum and larger numbers towards the beginning of the array that you can subtract from the sum. In that case you would have added more numbers than you would subtract contributing to a longer subarray
I love this kind of videos.Keep up the good work man
A naive nested loop has worse efficiency than you might think. There are O(n^2) ranges calculate sums for. Calculating the sum of those ranges is not O(1), since the length of those ranges is proportional to n. Of course, you can trivially change the naive algorithm to O(n^2) by filling in every possible sum into a 2D array (i.e., by using dynamic programming). That said, the problem constraints guarantee that array members are always >= 0, so the sliding window approach is far superior.
Since the first 8 array elements sum to 15, you would then only need to check subarrays of length 9 or longer (starting at elements 2, 3, 4, and 5). Once you don't find any of length 9 and all of those length 9 sums are more than 15, you would be done.
Some people think that two nested while loops have time complexity O(n^2). pay attention to the explanation the pointers never go back to the start of the array they just move in one direction so linear time
9:02 is that really necessary? Why check the sum, when you already know the current subarray you're checking has less items than the subarray we found earlier, which is 8 items long? No way it will be the longest subarray. Shouldn't you move the yellow arrow instead?
You're right. This could be solved by incrementing both pointers instead of only the left pointer if r != [-1] (in the given situation)
Impressive as usual it all about how you describe the answer and the problem I hope many creators learn from you
You didn't have to freeze right pointer until you have current_sum equal to given sum (while moving left one further). You could just slide the window for 9 elements to the right until it's less or equal of the given sum. Your goal is to find a window with more than 8, so, why shrink it?
Most optimal soln : Kadane's algorithm and it will work in O(n) time for even negative elements.where sliding window fails !!
OH MY GOD! So I've been watching your videos and solving these questions for the past 4 hours. I could finally come up with the right solution this time. I'm not so rusty after all! So pumped rn! lol
I totally agree. Some of the problem description often make things look more complex than it should. I tend to read them like 3 times to make sure I understand it.
You write so clean code than other TH-camrs out there. Impressed!
instead of storing result as as an array of left and right variables, we can just store the current maximum length of the subarray sum. Then if right - left is greater than result we update result as right-left.
The solution requires the range, not just the length of the range.
how about sorting the array first, then start with the moving window and return the first found solution? since all the numbers next are bigger, so it cant become longer. worst case is worst here, but average should be (maybe) better?
Me: See's thumbnail
My Brain: Ara Ara
Can we solve this problem by : 1. Sort array in ascending order
2. Add up the sum for each array element
I think it also require O(n).
So, can we solve the problem by this approach?
Sorting is NlogN which is slower than O(N)
@@NickWhite Get it. Thanks
that wouldn't work. How do you determine the indices after the fact? What if there are repeated values - which one's which? Is your sort stable? But mostly you're completely changing the order of the values in the original array so you lose cohesion.
If you want another solution you could:
1.Create an array pref[i]=arr[i]+arr[i-1]+...arr[0] O(n)
2. So now if we want the sum of the segment arr[i...j] we can do pref[j]-pref[i]+arr[i]
3. We can try some binary search stuff for every i=0...n-1 which would take O(nlogn)
So yeah his two pointers solution is much better.
Sorting would not work because it will mess up the order. We need the subarray, not any combination to reach the sum
Can you please read the problem description in your next videos, as it helps simulated a real life coding interview
At a real life coding interview, you can always ask the interviewer for clarification of the question if needed. Imagine this just simulating the clarification of the question.
HIGH Quality content!! Gonna watch all your Leetcode qns interview now to help me prepare!!
Make more of this please! Thanks!!
Excellent job describing these algorithms! I wish I had videos like these when I first started my career in software engineering!
If there were negative numbers in the array, you'd have to keep going through using the left pointer, correct? Because you could hit 15 again.
if there were negative numbers in the array, this algorithm will not work, you have to use prefix sum. Because this algorithm is base on a rule that if you expand the right -> the sum will increase, if you shrink the left -> the sum will decrease. Unfortunately that's not the case for negative numbers.
Wondering how to solve this if I have negative numbers in the array :/
this doesn't work with unsorted arrays
I guess the array must be sorted for this approach to work
Are negative numbers allowed in input array? I missed it, but I guess not allowed. Because I can make counterexample input like [a0, ..., aN, -sumOfThose + desiredSumOfSubarray]
Why does the array begin with element 1? Shouldn't it begin with element 0?
I am thinking can I stop the loop check if the difference of 2 elements in result array is larger than the arr.length - left
Assuming I understand you correctly, then in that case, right would be equal to arr.length. And thus the answer must be yes, since you cannot create a longer array.
Edit: Assuming r != [-1]
If arr=[1,2,3,7,5] and sum = 9 the longest sub array adding up to 9 is [1,3,5] this algorithm will not find it because it only works for contiguous subarrays and it would be beneficial to state so in the problem description in the beginning of the video.
I wee where you're coming from, but subarrays can only be continuous. [1,3,5] is not a subarray of [1,2,3,7,5]. Imagine a subarray like being a slice of the array.
A sub-array is not a sub-set.
@Nick White Thanks again for great explanation. Can you please answer just one more question
I tried solving this question on my own before looking at this video on CodeSignal, I could solve it with single loop & sliding window however it couldn't cover the edge cases like *(new int[]{1, 0, 2, 0, 0, 0, 0, 0}, 0);*. I spent 2 hours figuring out a solution that'd work for both normal cases & edge cases, however I couldn't.
The question is: Did you solve this question on your own, if so, how long did it take you to solve it? Second, if not, did you watch someone else's solution & than understand that solution to solve this problem?
I feel like I'm not good enough since I couldn't solve it on my own & I had to look at other's solutions to figure out a solution. This is making feel worried if I'm good enough for the coding interviews at Big companies like Google, Facebook, Microsoft or Amazon.
How would you do this if instead of an array/list, it was a set, so find the longest set of numbers that add to the sum (where order doesn't matter)?
Would you have to store every single set that doesn't add up to greater than S?
Nice solution. Another idea is prefix sum and binary search, but two pointers is much better.
Porco-espinho Entediado you cannot do binary search since the array is not sorted. The prefix sum will not be sorted either because negatives will decrease the sum
I don't know if my solution is more efficient or not but still, here it is :
Step 1: sort the array in ascending order
Step 2: loop through the sorted array and keep adding the elements until the sum becomes equal to the given no.
Step 3: Once the array sum becomes equal to the given number pick the positions and return them.
Sorting would mess up the order of the array.
In addition to what Ankit said: sorting has a best case time complexity of O(n log n).
So Nick's algorithm would return the correct answer before you even finish with your first step (since Nick's solution is O(n)).
(Side note: not that I could do any better, either. I only managed to come up with a O(n^2) solution before seeing Nick's solution.)
I understood the optimal solution because you explained it clearly, but couldn't understand the brute force solution 5:33 (you just said "keep going, next one, look at all of em") pls explain brute force solutions clearly too.
Bruteforce solution:
(If at any point the sum of a subarray is equal to s, you have the answer)
- First check if the sum of the whole array (of length n) is equal to s.
- Then check if any subarray of length n-1 is equal to s.
- Then check for any sub
array of n-2 ...
- Continue until you've checked all subarrays of size 3, then 2, then 1..
- If you still haven't found a subarray with sum s, then there is none and you return [-1].
I love thos channel. We want videos like this... All your videos are great @Nick.
Indexes are zero based. There is no need to add 1.
If one pointer reached end and the distance between the other array is less than current max length we can exit the loop early ?
This question's difficulty level would increase 69X if it has negative numbers too
so Nick, there's one thing I'm not quite getting - you say that you hope people can nail problems like this and get a job. You're a Leetcoding monster yet - I believe - you haven't got an offer yet? Is it because even rehearsing all the Leetcode, Facebook, Google, Amazon, blah blah questions in the world won't help in a live tech interview, or is there something else (the hemp debacle at Google notwithstanding)? It seems to me that on the basis of answering coding questions you should definitely be hired. It's a bit worrying if that's not the case. What does it take?!?!? Does this also mean that all these coding sites that are popping up from various youtubers are selling snakeoil if it makes no difference, regardless of the reams of testimonials they supposedly have (I'm very doubtful: at least one of those guys is a known BS artist). Thanks and good luck!
I’ve gotten plenty of offers
I currently have a job and also have had plenty of positions in the past please watch my video from save a lot to $55 / hour or you can see my LinkedIn in description
@@NickWhite OK, sorry: I mustn't have watched enough vids yet. I obviously came to the conclusion that you have been interviewing but no-one has seen fit to extend an offer. You're obviously a talented engineer so it'd be worrying if even someone with such a track record of solving problems is not getting offers. I hope you continue with the channel. Much respect for you and your many talents (not least the songs :D)
Didn't realize this would work as long as it's positive. I thought this approach only works if you sorted the array...
So if negatives were involved, prefix sum is the answer?
You can stop once the remaining length is lesser than the current longest length.
Is there a possibility where the left pointer > right pointer ?
Could someone please explain to me how you decided to start off from 2,3,4.
I don’t really understand the concept of the whole contiguous sub array
This algorithm works only if the int array are all positive or non negative
in the video I say that the elements are all positive
got it, got it. My bad. :-) and forgot to mention that all your videos are good, keep up!
why the yellow pointer doesn't just start from the end of the array and decreasing it , this will directly get the longest possible subarray
Hi Nick..nice job...
But one important question...
Doesn't this approach looks like the elements in the array should be sorted...as you are popping out the LHS elements on the sum being greater than S??
I thought the same thing. I didn't think it would work on an array like [0, 0, ... numbers, 0] since it would likely pop off the initial 0s at some point. But then I thought about what a sub array really means, and its likely the problem doesnt allow you to pick numbers that arent adjacent. Like if you did a slice on the array.
Dude, the way you explain the solutions is just awesomeeeeeee.
We want more of this.
Will the while condition work for input like:
[1,1,1,1000], sum=100
?
I have got a question. I think your first example was wrong. Index of 2 was 1 in your array. I don't know Java's indexing rules but it's wrong in python. And, I want to publish my python answer:
def findLongestSubarrayBySum(arr, s):# O(n^2) O(1)
r = []
for i in range(len(arr)):
for j in range(i, len(arr)):
if sum(arr[i:j]) == s and len(arr[i:j]) > len(r):
r = [i, j]
return r
It took me more than an hour but I actually came up with the O(n) solution by myself.
Love from India ❤️ thanks. Brother for making these types of videos .
Very Nice Explanation Nick.......Keep the momentum going on.
5th Element? That would be Milla Jojovich
Leeloo Dallas Multipass :)
Find the maximum number after adding n number of comma example 455 and count of comma is. 1 then 4,55 so maxnumber is 55 can you find suitable solution of it
I don't understand, I feel there are use cases where this wouldn't work. For example (looking for a sum of 15)
[5, 11, 10]
The window wouldn't see any arrays that add up to 15.
Edit: I see now that it's consecutive elements.
this is better
int[] result = new int[], {-1,-1};
int left =0;
int sum = arr[left];
int right = 0;
while(right < arr.length)
{
sum +=arr[right];
if(sum == s)
{
result = new int[] {left,right};
right++
}
else if(sum>s)
{
if(right-left>result[1]-result[0])
{
sum-=arr[left++];
}
else
{
right++;
}
}
return result;
Cant we move both the left and right pointers together?! after all the window was longest :/ so just moving the left slider is only gonna make it small which is not a desired result anyways
Are you not using zero indexed array?
The inner loop does not depend on n but it does iterate some m times, so the complexity is still O(n.m) right?
Correct me if I am wrong.
The left and right pointer will both only move to the right. They can thus only move O(n) times, and since the rest of the algorithm is constant time for each configuration of pointers, the algorithm is O(n)
Cool.
@@madhavtibrewal6614 To elaborate, for any constant c, O(c*n) = O(n).
How do you come up these solutions??
Hi! What will happen if I try to go from the begin and the end of the array, moving borders to each other while sum inside is not equal to the value (comparing arr[left] and arr[right] and deleting from subarray the biggest)? I'm feeling something will go wrong, but can't catch what.
your approach seems O(n^2) to me but can you explain how will to add the elements in a variable if your first pointer is at the start I mean which pointer you are using for adding and which for subtracting the values from sum
Loved this ,new way of explanation
This solution, seems to fail for this kind of case:
arr = a = [-2, -3, 4, -1, -2, 1, 5, -3]
s = 6
given the constraints where we are guaranteed only positives. If that were removed, is it possible to tweak this to result in a correct solution too?
Your case as no solution, but this code will tell you :
function findLongestSubarrayBySum (arr, s) {
var len = arr.length;
var deb = 0, fin = 0, sum = 0;
var r = [-1], ln = 0;
while (deb < len) {
for (; sum ln) {
ln = fin-deb;
r = [(deb+1),fin];
}
}
for (; (sum > s || fin >= len) && deb < fin ;) {
sum -= arr[deb]; deb += 1;
if (sum === s && fin-deb > ln) {
ln = fin-deb;
r = [(deb+1),fin];
}
}
}
return r;
}
7:09 I was thinking the same when you said it.
Nice problem. Thanks for explaining, Nick.
Loved this video!
But this solution won't work for negative values.
Example: arr =[-1,-1,1], s=0
please reply !
is it necessary to solve the problem in a particular programming language or is it left as a choice ?
What if there are negative numbers in the array??
r= [1,3] first element is index 0
In the problem description it says that the output should be 1-indexed, not 0-indexed (they call it 1-based)
Love your work in youtube ! Great algo and good question. Ty you're helping me :2
how it's linear, because there is two while loop in it????????
is the similar ques available on leet code?
no i too tried to searched it on the LC,but didn't find it,if you think there is ,then pls share the link here.
can anyone give me the link to this problem ??
the link that nick gave go to the home page of coding signal .
Loved this new way of ur explanation
r=[1:3], not r[2:4] since it starts from index 0
2:48 - you need to go back to school and learn your powers of 10. 10^5 is not 10,000 and 10^4 is not 1,000.
Even if the array is not sorted?
Yes. The video includes an example of this algorithm being used on an unsorted array.
Give the tried history or give us link. Main thing is understanding the problem. We fail in that stage.
keep going Nick! thank you
If right is as the end, you can return if the current window size is < the size of the current result or if the window sum is > the target sum. In those cases, you already know that further sums can't satisfy the condition.
Wow what an amazing explanation. Thanks bro !
U’r a genius and I really like your videos
That's a nice approach
Love your vids! I always learn new cool stuff!
Very good explanation. Thanks!
Well explained. keep posting.
nicely answered (y)
10^5 is a 100k not 10k, and 10^4 is still not a 1000.... int left n right are not pointers
Amazing video! Keep it up!
Nicely explained
Thank you for the explanation Nick.
Can you think about starting a Ds Algo Series from scratch, so that beginners like me can learn from a great teacher like you?
I can recommend the videos done by Robert Sedgewick. If you want additional reading that matches the videos, they follow the structure of the book co-authored by Sedgewick himself.
Love from Taiwan, thanks so much.
Nice explanation and please keep going.
Hey nick, great video.
One thing is that I really think that in addition to your explanation of the problem, you should add the formal question on the side. In this particular problem you didn't mention the fact that the array has to be non negative which is crucial for the linear solution.
Or at least if you indeed allow negatives, you have to make the array non negative and update the target as well
@@omerronen2329 its in the constraints, he did mention it
@@hamzasayyid8152 Well I didn't notice on my first hear. This shows my point
@@omerronen2329 2:58