There is also an nlogn solution where you can use two vectors prefix and suffix vectors and then start travelling the prefix vector from i=0 and suffix vector from j=n-1 and since these are sorted if you find a particular element of the prefix p then we can apply binary search on the suffix and vice versa there will be some edge cases for like n=1 which you have to handle
Actually it is very simple. If we use hash map O(n) Store sum as key form ending of array and pair as it's index. Then iterate from Starting and finding if x- currentSum is in dictionary. So simple
Instead of checking on every iteration whether the left pointer crosses the right one, you could also just check whether the target is negative once at the start and early return in that case.
He actually says target < 0 is part of the reason left and right could cross when it is actually the whole reason He has a bias towards unnecessary checks in loops that felt inefficient at first but doesn't seem to affect runtime. I don't know how it plays in interviews.
the most awesome explanation i have heard for this question! (though i nearly lost all my confidence when you said this is a generic sliding window -.-)
Great question, can be confusing but note the ordering, since r always points to a valid element, in the real and valid case that l == r == len(nums - 1) it will first subtract the element from l which is the last element and is valid, l (left) will then increase out of bounds but the for loop will terminate at the top because r is at its max and we never access the element at left after we increment it potentially out of bounds. So our code may end with l == len(nums), an invalid index and right and left have crossed which we usually hate, but at that point everything is guaranteed to terminate and we never access those elements at those pointers again and thus never have to check for those conditions.
I saw it as 2sum where you create a dictionary of prefixes and then iterate backwards and find if x-postfix exists in the prefix dictionary. Interesting problem with a lot of approaches.
Why cant I duplicate the array to the right and find the smallest sum subarray. It works for most of the cases but fails at a few of them? Smth like the Min No of flips to make binary string alternating?
class solution { public int min Operation (int []nums,int x){ int target =-x; for(num:nums) target +=num; if(target ==0) return nums.length; int sum =0,i=0,res=interger MIN_VALUE; for(int j=0;j
Isn't it possible to use 2 pointers...assign the left and right to start and end respectively and from the 2 pointers take the maximum of the 2 to minimize the operations?
![Diggy Graves - Red Vineyard [Official Lyric Video]](http://i.ytimg.com/vi/8Ro085T0mnQ/mqdefault.jpg)
Damn! This is a tough solution to come up with.
That one problem of bit masking+ dp + trees , you didn't made video on that 🙂
yeah man, hard for chumps like me to solve
There is also an nlogn solution where you can use two vectors prefix and suffix vectors and then start travelling the prefix vector from i=0 and suffix vector from j=n-1 and since these are sorted if you find a particular element of the prefix p then we can apply binary search on the suffix and vice versa there will be some edge cases for like n=1 which you have to handle
Actually it is very simple.
If we use hash map O(n)
Store sum as key form ending of array and pair as it's index.
Then iterate from Starting and finding if x- currentSum is in dictionary.
So simple
THANK YOU SO MUCH, but his solution is more efficient since you are using a hash map the memory will be O(n) and the memory in his code is O(1)
"so simple" 🙄
Instead of checking on every iteration whether the left pointer crosses the right one, you could also just check whether the target is negative once at the start and early return in that case.
He actually says target < 0 is part of the reason left and right could cross when it is actually the whole reason
He has a bias towards unnecessary checks in loops that felt inefficient at first but doesn't seem to affect runtime. I don't know how it plays in interviews.
the most awesome explanation i have heard for this question! (though i nearly lost all my confidence when you said this is a generic sliding window -.-)
Why is it l
Great question, can be confusing but note the ordering, since r always points to a valid element, in the real and valid case that l == r == len(nums - 1) it will first subtract the element from l which is the last element and is valid, l (left) will then increase out of bounds but the for loop will terminate at the top because r is at its max and we never access the element at left after we increment it potentially out of bounds. So our code may end with l == len(nums), an invalid index and right and left have crossed which we usually hate, but at that point everything is guaranteed to terminate and we never access those elements at those pointers again and thus never have to check for those conditions.
Such a clever question. Did you come up with the Sol on your own?
Before today I thought I knew 2 pointers. That was my only weapon in these contests. Now I realize I am a dummy!!
Awesome and simple solution, thanks.
We can solve this using binary search on number of elements to remove.
Amazing explanation as always. Thank you
is it possible to solve this problem using a greedy algorithm? I was wondering
Can you please solve that problem 3 days back which included bit masking + bfs
I saw it as 2sum where you create a dictionary of prefixes and then iterate backwards and find if x-postfix exists in the prefix dictionary. Interesting problem with a lot of approaches.
if i took the larger number from both sides and then subtract the the larger number from x and count it as a step, will this work?
no this doesn't work. For example, lets say you had x =5 and nums = [2,2,1,2,10,4], your algorithm would subtract 4 first then 2 which will never work
@@impolitebigmac3044 oh thanks for the explanation
That's what I did initially. Greedy approach. Failed after 45 test cases
Hi there, actually I need a help regarding a question ,tell me how can we connect
Very Good explanation
Why cant I duplicate the array to the right and find the smallest sum subarray. It works for most of the cases but fails at a few of them? Smth like the Min No of flips to make binary string alternating?
12:07 is the secret to sliding window
excellent, thank you :)
Thank you
You’re totally awesome
you're the goat sir ty
damm how can i even imagine this can be done like that
res=MATH.MAX (res,j-i+1);
one correction
What would the recursive solution look like?
Um.. the array nums is sorted?? They never mentioned about it right??..
No, I don't think the array is sorted. Check the example.
Why would it be sorted?
Got it 😅
thank ya
Awesome
class solution {
public int min Operation (int []nums,int x){
int target =-x;
for(num:nums)
target +=num;
if(target ==0) return nums.length;
int sum =0,i=0,res=interger MIN_VALUE;
for(int j=0;j
🙏
Isn't it possible to use 2 pointers...assign the left and right to start and end respectively and from the 2 pointers take the maximum of the 2 to minimize the operations?
I tried it and didn't work
the blue stuff
awesome explanation