If you've been following this series so far, then this problem should be a piece of cake.

# Problem

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

**Example:**

```
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
```

**Note:**

You must do this in-place without making a copy of the array.

Minimize the total number of operations.

# Approach 1

**Algorithm:**

- Initialize variable zeroCount to store count of zeroes
- Initialize result to store the final array
- Iterate through all elements of the array
- If the element is zero then increment zeroCount
- Else append to the result array
- Append zeroCount number of zeroes to the result
- Replace elements of original array with result

**Code:**

```
def approach1(nums):
zeroCount = 0
result = []
for i in range(len(nums)):
if nums[i] == 0:
zeroCount += 1
else:
result.append(nums[i])
for i in range(zeroCount):
result.append(0)
for i in range(len(nums)):
nums[i] = result[i]
return nums
```

**Complexity analysis:**

```
Time complexity: O(n) Always n operations
Space complexity: O(n)
```

# Approach 2

**Algorithm:**

- Initialize variable nextIndex to store the next index of non zero element
- Iterate through all elements of the array
- If the current element is not zero then put it at nextIndex and increment it
- Once step 2 ends iterate from nextIndex to the end of the array and assign zero at those indices

**Code:**

```
def approach2(nums):
nextIndex = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[nextIndex] = nums[i]
nextIndex += 1
for i in range(nextIndex, len(nums)):
nums[i] = 0
return nums
```

**Complexity analysis:**

```
Time complexity: O(n) with near minimum operations
Space complexity: O(1)
```

# Approach 3

**Algorithm:**

- Initialize variable nextIndex to store the next index of non zero element
- Iterate through all elements of the array
- If the current element is not zero then swap it with the element at nextIndex and increment it

**Code:**

```
def approach3(nums):
nextIndex = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[i], nums[nextIndex] = nums[nextIndex], nums[i]
nextIndex += 1
return nums
```

**Complexity analysis:**

```
Time complexity: O(n) with minimum operations
Space complexity: O(1)
```

# Summary

This problem was more of tricky thinking rather than algorithmic thinking.

Here's the replit

## Top comments (0)