Move zeroes | Leetcode
Vložit
- čas přidán 3. 04. 2020
- This video explains the day-4 problem of leetcode 30 days coding challenge in april 2020. I have explained the problem with given constraints in mind using example and code. This video first explains the simple approach and then an intuitive approach of solving the problem using two pointer technique. It solves the problem in O(N) time and O(1) extra space with inplace algorithm. As usual, CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
thankYou for the explaination..keep up the good work...
thanks for uploading,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,your method is always better.
Thank you. You made the solution look very simple. Appreciate it!
Thanks
instead of taking extra variable temp we can use in built swap function.
Nicely explained. Wow. We can avoid swap. Take count=0 and whenever we see non zero arr[counter++]=arr[i] and in last if counter
Nice idea :)
Isn't this a bad idea if all the elements in the given array are zero, then both right pointer and counter is going to iterate through the entire array.
Where as if we do swap, we'd be iterating only once both pointers put together.
instead of taking extra variable temp we can use in built swap function.
We don't need to worry about the size condition:
int p1=0,p2=0;
while (p2
sir explains the best , i solved it but came to like ur video thank you sir👏❤️🤗
😁
Good stuff brother, two pointer technique optimal solution
instead of taking extra variable temp we can use in built swap function.
Nice video,Thank you bro.
Welcome :)
Amazing Approach
Sanskar Kumar The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)
Two pointer technique 😎
i am a python programmer just come see explaination very helpful
Nice explanation!
Same 2 pointer approach, but without swap
void moveZeroes(vector& nums) {
if(nums.size()
instead of taking extra variable temp we can use in built swap function.
really appreciate this code anjali
Ur contents r really good
Thanks :)
In Javascript
function moveZeroes(arr){
let counter = 0;
for(let i=0; i < arr.length; i++){
if(arr[i] !== 0){
arr[counter++] = arr[i];
}
}
while(counter < arr.length){
arr[counter++] = 0;
}
return arr;
}
Thanks :)
well explained
Good solution. But, I think full swap logic is not required by creating extra variable temp. As we know element to be swapped is fixed 0. Something like this will work. nums[i] = nums[j];
nums[j] = 0;
you need swap logic otherwise it will fail for [1,0] input
instead of taking extra variable temp we can use in built swap function.
So basically we don't have to shift zeros to the end , we have to shift non zeros to the front . Cool 🔥 👍
instead of taking extra variable temp we can use in built swap function.
Great explanation! Really appreciate it.
first I counted the number of zeroes, then I removed all zeroes using STL erase and remove. Then I pushed back the number of zeroes that I counted earlier.
Time Complexity is O(n) only and Space Complexity is O(1), because I just used an extra variable to store number of zeroes
ig on lc for this u will get MLE
When you remove a zero from the list, you have to shift all the items afterwards down an index, which is O(n). So your method would be O(n^2).
Nice video bro
Thanks :)
nice video
Thanks :)
@TECH DOSE You said in the video..if you have a better logic then let me know.....So I will just provide a Python code where it still can be thought as a 2 pointer approach with the left pointer and the right pointer being the array traverser .....The same logic can be implemented in Java, C or C++ or any other language according to syntax...
left = 0
for index in range(len(nums)):
if nums[index]:
nums[left], nums[index] = nums[index], nums[left]
left+=1
Thx!
instead of taking extra variable temp we can use in built swap function.
Yes
👌🏽👌🏽👌🏽
Dilip Suthar The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)
Dilip Suthar The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)
This code is showing time exceeded.. :(
void moveZeroes(vector& nums)
{
int i=0;
int x=0;
while(i
can you tell me why can't this algorithm is not passing all the test cases:
class Solution {
public:
void moveZeroes(vector& nums) {
vector:: iterator itr = nums.begin();
int count = 0;
for(int i=0; i
Hi sir can you tell why it's++right instead of right++?
Hello sir, I want to learn about time complexity and space complexity. How we calculate it is o(n) or o(log(n). Any tutorial are there for that? your explaination is so good.
watch any video on time complexity
thank u
Welcome
Your code is not working for this data {0,1,0,3,12}.
If first element is non zero and second element is also non zero like [1,2,4,6] then after first swap array will change to [2,1.....] Which is not allowed so if first element is nonzero then what we do ?
#include
using namespace std;
int main()
{
int n;
coutn;
int arr[n];
cout
I had the same doubt.
Since left and right are both starting at the same point the swap happens with the same number. Hence 1 is swapped with 1 and both pointers are incremented by 1.
Tweak the algorithm a little bit to skip swapping number with itself
@@mohammedthahajk7619 instead of taking extra variable temp we can use in built swap function.
Also make the feb 2021 leetcode playlist
It won't be possible 😅 I will start hashing now
@@techdose4u okay 🤗
How do you handle the two pointers' method with the following inputs?
int[] nums = new int[]{1, 3, 12,0,0};
int[] nums = new int[]{1, 3, 12};
You can dry run this input using 2-ptr technique. When swap happens then left and right are actually pointing to the same value and so element remains at the same position. Nothing is altered :)
@@techdose4u we can modify program by adding extra check that swap only if left pointer is pointing to 0(zero).can we?
It can reduce the number of swaps but it is adding extra condition check.
So, which is batter,
more swaps and less conditions
Or
Less swaps and more conditions
????????????
Actually you should not put condition for left but only right. This will make the logic much simpler. You can add a case if both left and right are pointing to same index then increment both (if value is not zero) otherwise if they don't point to same index then left will always have zeroes. So this logic won't work. We want to swap when right points to zero and not left. I hope you got the point. Take some examples and see.
@@techdose4u yes, I got your point but i just want to ask you
which is batter,
more swaps and less conditions
Or
Less swaps and more conditions
????????????
@@techdose4u instead of taking extra variable temp we can use in built swap function.
Bro if we not write if(n==0 ) ||n==1) the code will run?
Yes it will run :)
what about using a queue instead.. when find zero push to the bottom
Don't use queue. Instead just count the 0s using a counter variable.
@@techdose4u ok sir :)
Hello, your approach is so elegant but you forgot to write return array. However, thanks
😅 welcome
Sorry, here we don't want to return anything
instead of taking extra variable temp we can use in built swap function.
thanks for the explanation, but how would you answer if the requirement is to move all zeros to the beginning
Just interchange the if code and else code.
What is the first two elements are zero?
Try to dry run. Its simple. You will get it.
void moveZeroes(vector& nums) {
for(auto it=nums.begin() ; it != nums.end() ;it++){
if(*it == 0){
nums.erase(it);
it--;
nums.push_back(0);
}
}
}
why is this giving TLE?
What if the 0th element is non zero?
Swapped with itself. Both left and right pointers move ahead. Problem space reduced by 1.
we need to swap only when val @ left pointer == 0 and right_pointer not equal to zero;
summary of the solution:
- 2 pointer left and right initially at 0
- repeat until right @ end of array:
r == 0: increment right
r != 0
- left == 0 => swap left and right pointer val
- left != 0 increment left and right pointer
instead of taking extra variable temp we can use in built swap function.
I would suggest to submit solution a day later
It's true that you should first solve it and then see the video. Solutions become available once you solve it. I will post the videos late anyways in weekdays. Does it create any problem for others? Do you find any inconvenience ?
@@techdose4u actually I think when solution is there we don't push ourselves enough to solve by own
Yea true. But actually you should try the question first and solve it. It is not advised to spend the entire day on these questions. Actually answers are available at many sources of CZcams itself during the competition. But I would advise you to not watch the video. Only when you have fully tried then only watch. You should make this resolve. I hope this should be fine. Anyways on weekdays you won't see me post early due to my own work 😅
@@techdose4u yeah! BTW thanks for all these videos they are really helpful and also Google codejam was till today if u could post videos from there it will be highly appreciated
Why ++left, and not left ++
If first element is non zero then when we r never incrementing left
If element pointed by right pointer is not zero then we swap with left otherwise we just increment right ptr.
Well in the beginning both left n rt pointer points to 1st elt
Since it is non zero swap will happen but since both index are same swap is meaningless and both pointer will move fwd. Hope youve got my point 🙂✌️
czcams.com/video/ScwiXBGyVz4/video.html
If the first element is non zero then what to do🙄
Bro start, i with 0 and j with 1:
Conditions:
>> if(i==j || arr[i] == arr[j]) { j++; }
>> else if(i!=j and arr[i]!=0) { i++, j++; }
>> else { arr[i]=arr[j], arr[j]=0, i++, j++; }
By this approach, if the first element is non zero then both i and j will be increamented.
/*the easiest implementation*/
int s=nums.size();
int i,k=0;
for(i=0;i
how to think like this
Practice :)
wrong aa rha h run krke yeh soln
Your statement is incorrect here 3:16
hey tech dose please make video in hindi so that we can understand easily
Hindi will not be possible bro. Those who are programming will obviously have to learn English and appear for interviews in english language only. So you should try to understand English. If you need any advice then ask me because I was not able to speak English myself in college 😅
i understand english but but we understand more easily in hindi
because hindi is our mother tongue
that's why i said that
True. But you need to get good at english quickly because software companies always prefers communication skills. It is extremely important.
ya i heared about that
#include
using namespace std;
int main()
{
int n;
coutn;
int arr[n];
cout