Move zeroes | Leetcode

Подписаться 174 тыс.

Просмотров 45 тыс.

50% 1

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.co...

Опубликовано:

16 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 113

@guptasaurabh688 4 года назад

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

@techdose4u 4 года назад

Nice idea :)

@anujithsingh4868 2 года назад

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.

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@life_of_anjali 3 года назад

Nice explanation! Same 2 pointer approach, but without swap void moveZeroes(vector& nums) { if(nums.size()

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@SHRUGX_YT 2 года назад

really appreciate this code anjali

@yashpreetbathla4653 4 года назад

sir explains the best , i solved it but came to like ur video thank you sir👏❤️🤗

@techdose4u 4 года назад

😁

@dondondonify 3 года назад

Thank you. You made the solution look very simple. Appreciate it!

@techdose4u 3 года назад

Thanks

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@sandeepmenta9579 4 года назад

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; }

@techdose4u 4 года назад

Thanks :)

@shinku100 4 года назад

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;

@Alikhan1993 2 года назад

you need swap logic otherwise it will fail for [1,0] input

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@siddhanttiwary 4 года назад

We don't need to worry about the size condition: int p1=0,p2=0; while (p2

@eyasir2047 2 года назад

Two pointer technique 😎

@RohanSaluja 2 года назад

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

@supriyamanna715 Год назад

ig on lc for this u will get MLE

@Kevin-xp1dp 9 месяцев назад

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).

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@techdose4u 2 года назад

Yes

@sabyasachisahoo8975 2 года назад

thanks for uploading,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,your method is always better.

@jsarvesh 3 года назад

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

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@sagarpatel8853 2 года назад

thankYou for the explaination..keep up the good work...

@ronsinha21 Год назад

@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

@hardikshreyas8540 2 года назад

i am a python programmer just come see explaination very helpful

@sanskarkumar7984 4 года назад

Amazing Approach

@raghukumar2874 4 года назад

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:)

@vinayak186f3 3 года назад

So basically we don't have to shift zeros to the end , we have to shift non zeros to the front . Cool 🔥 👍

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@vireshdeshamane 2 года назад

This code is showing time exceeded.. :( void moveZeroes(vector& nums) { int i=0; int x=0; while(i

@koushiks9292 4 года назад

Ur contents r really good

@techdose4u 4 года назад

Thanks :)

@codeisgoodbro1810 3 года назад

Good stuff brother, two pointer technique optimal solution

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@shubham007121 4 года назад

nice video

@techdose4u 4 года назад

Thanks :)

@ashokjat555 4 года назад

Nice video,Thank you bro.

@techdose4u 4 года назад

Welcome :)

@abhaythakur2597 Год назад

well explained

@navinchainani4721 4 года назад

Nice video bro

@techdose4u 4 года назад

Thanks :)

@divyamaheshwari4066 3 года назад

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.

@RamKumar-kz8gg 2 года назад

watch any video on time complexity

@jasmeenkaur6001 3 года назад

Also make the feb 2021 leetcode playlist

@techdose4u 3 года назад

It won't be possible 😅 I will start hashing now

@jasmeenkaur6001 3 года назад

@@techdose4u okay 🤗

@sabrinarahman2156 3 года назад

Hello, your approach is so elegant but you forgot to write return array. However, thanks

@techdose4u 3 года назад

😅 welcome

@rohithv63 3 года назад

Sorry, here we don't want to return anything

@imshivendra 2 года назад

instead of taking extra variable temp we can use in built swap function.

@dilipsuthar4206 4 года назад

👌🏽👌🏽👌🏽

@raghukumar2874 4 года назад

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:)

@raghukumar2874 4 года назад

@sahilbisht3661 4 года назад

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 ?

@b.sainathreddy4567 4 года назад

#include using namespace std; int main() { int n; coutn; int arr[n]; cout

@mohammedthahajk7619 3 года назад

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

@imshivendra 2 года назад

@@mohammedthahajk7619 instead of taking extra variable temp we can use in built swap function.

@GurpreetSingh-ps6kl 3 года назад

thank u

@techdose4u 3 года назад

Welcome

@karthikeyanannamalai2805 4 года назад

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};

@techdose4u 4 года назад

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 :)

@yashgoswami5374 4 года назад

@@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 ????????????

@techdose4u 4 года назад

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.

@yashgoswami5374 4 года назад

@@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 ????????????

@imshivendra 2 года назад

@@techdose4u instead of taking extra variable temp we can use in built swap function.

@ilanaizelman3993 2 года назад

Thx!

@pritamsarbajna681 2 года назад

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

@riyarana1353 3 года назад

Great explanation! Really appreciate it.

@SurajGupta-zx5lj 4 года назад

what about using a queue instead.. when find zero push to the bottom

@techdose4u 4 года назад

Don't use queue. Instead just count the 0s using a counter variable.

@SurajGupta-zx5lj 4 года назад

@@techdose4u ok sir :)

@LDarshanKasar Год назад

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?

@awakashsinha9926 4 года назад

I would suggest to submit solution a day later

@techdose4u 4 года назад

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 ?

@awakashsinha9926 4 года назад

@@techdose4u actually I think when solution is there we don't push ourselves enough to solve by own

@techdose4u 4 года назад

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 RU-vid 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 😅

@awakashsinha9926 4 года назад

@@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

@pl5778 2 года назад

thanks for the explanation, but how would you answer if the requirement is to move all zeros to the beginning

@mayankbharti531 Год назад

Just interchange the if code and else code.

@stankafan6688 4 года назад

/*the easiest implementation*/ int s=nums.size(); int i,k=0; for(i=0;i

@paraslohia9292 2 года назад

What if the 0th element is non zero?

@sauravjos Год назад

Swapped with itself. Both left and right pointers move ahead. Problem space reduced by 1.

@akashacharya2143 Год назад

Hi sir can you tell why it's++right instead of right++?

@IamShivaniPandit 3 года назад

Your code is not working for this data {0,1,0,3,12}.

@santhipriyadinakaran 3 месяца назад

Why ++left, and not left ++

@navinchainani4721 4 года назад

Bro if we not write if(n==0 ) ||n==1) the code will run?

@techdose4u 4 года назад

Yes it will run :)

@randy4443 4 года назад

What is the first two elements are zero?

@techdose4u 4 года назад

Try to dry run. Its simple. You will get it.

@awakashsinha9926 4 года назад

If first element is non zero then when we r never incrementing left

@techdose4u 4 года назад

If element pointed by right pointer is not zero then we swap with left otherwise we just increment right ptr.

@anuabraham2524 4 года назад

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 🙂✌️

@Horodgamin 4 года назад

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-ScwiXBGyVz4.html

@aravindk8181 3 года назад

how to think like this

@techdose4u 3 года назад

Practice :)

@__nitinkumar__ 2 года назад

Your statement is incorrect here 3:16

@khuzhi.sharma 2 года назад

wrong aa rha h run krke yeh soln

@botkiller563 3 года назад

If the first element is non zero then what to do🙄

@rajeshg8649 3 года назад

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.

@abhaytiwari6411 4 года назад

hey tech dose please make video in hindi so that we can understand easily

@techdose4u 4 года назад

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 😅

@abhaytiwari6411 4 года назад

i understand english but but we understand more easily in hindi because hindi is our mother tongue that's why i said that

@techdose4u 4 года назад

True. But you need to get good at english quickly because software companies always prefers communication skills. It is extremely important.

@abhaytiwari6411 4 года назад

ya i heared about that

@b.sainathreddy4567 4 года назад

#include using namespace std; int main() { int n; coutn; int arr[n]; cout