the problem
Solution:
When I read the problem for the first time it came to my mind direct solution that I want to go through the array whenever I encounter zero I just remove it and when I am done I add them again.
But the removal procedure on a list in python will cost O(n), and we will do this inside loop that goes through our nums
array, so totally we will reach to O(n^{2}) for the whole procedure.
zeros = 0
for i in range(len(nums)): # O(n)
del nums[i] # O(n)
zeroes += 1
Then I thought okay what about using the python count()
function to count the 0's and use another array to contain all my non-zeroes items in it. Then add zeroes amount of 0 to the end of the new array and later on override our nums
array by this new array values because it requires not returning anything.
If you think a little bit you can see this approach will work better than the above as it will take only O(n), but we used an extra space which is O(n) as we copied everything to a new defined array.
You can see full code for this moveZeroes_2().
Then I thought no I want time O(n) with space O(1) can we do that!
Yes, of course, we can how by using two pointers the slow one will call it last_non_zero
this will hold my last non zero number, and the fast pointer will call it i
and this will hold my current element in the nums
array.
What we will do will just move along the array whenever we encounter non zero number will move it to the place where last_non_zero
pointer is located then increase this pointer by 1, and when we are done make another loop starting from where last_non_zero
is to the end of the array and just keep adding zeros.
- Example:
nums = [0,1,0,3,12]
- We will start with
last_non_zero = 0
,i = 0
- check does
nums[i] != 0
, no it is not (nums[i] = nums[0] = 0
) increase the
i++
and check again, yesnums[1] != 0
as it is1
so move it to thenums[last_non_zero] = nums[i]
and then increaselast_non_zero ++
Now our array looks like thisnums = [1,1,0,3,12]
keep repeating this procedure until the end our array will look like this
nums = [1,3,12,3,12]
andlast_non_zero = 3
.Now we start from
last_non_zero
to the end and just add0
as we go so our final result will benums = [1,3,12,0,0]
- Pseudocode:
1. define `last_non_zero = 0`, `n = len(nums)`
2. loop from i = 0 to n:
3. if nums[i] != 0:
4. nums[i] = nums[last_non_zero]
5. last_non_zero += 1
6. loop from j = last_non_zero to n:
7. nums[j] = 0
Complexity:
Time complexity is straight forward O(n)
Space complexity we didn't use any extra space so it is O(1)
Solution: moveZeroes()
There is an optimal solution for this problem tries to find it out yourself :).
Top comments (0)