Minimum Operations to Reduce X to Zero - Leetcode 1658 - Python
Vložit
- čas přidán 25. 07. 2024
- Solving leetcode 1658, minimum operations to reduce X to Zero, today's daily leetcode problem on september 19.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:35 - Drawing Explanation
9:09 - Coding Explanation
leetcode 1658
#neetcode #leetcode #python
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
Amazing explanation as always. Thank you
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
Awesome and simple solution, thanks.
Very Good explanation
Before today I thought I knew 2 pointers. That was my only weapon in these contests. Now I realize I am a dummy!!
Can you please solve that problem 3 days back which included bit masking + bfs
you're the goat sir ty
awesome explanation
Such a clever question. Did you come up with the Sol on your own?
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.
excellent, thank you :)
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?
You’re totally awesome
Thank you
We can solve this using binary search on number of elements to remove.
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.
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?
thank ya
Hi there, actually I need a help regarding a question ,tell me how can we connect
Awesome
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
What would the recursive solution look like?
is it possible to solve this problem using a greedy algorithm? I was wondering
damm how can i even imagine this can be done like that
12:07 is the secret to sliding window
🙏
res=MATH.MAX (res,j-i+1);
one correction
the blue stuff
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 😅
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