**Difficulty:** Easy, **Asked-in:** Facebook, Amazon, Uber, LinkedIn, Bloomberg

**Key-takeaway:** An excellent problem to learn problem-solving using loop two pointers where both pointers are moving in the same direction.

### Let’s understand the problem

Given an array X[] of n integers, where some elements are zero and some elements are non-zero. Write a program to move all the zeroes to the end of the array.

**Example 1**

Input: X[ ] = [4, 8, 6, 0, 2, 0, 1, 15, 12, 0]

Output: X[ ] = [4, 8, 6, 2, 1, 15, 12, 0, 0, 0]

**Example 2**

Input: X[ ] = [0, 3, 5, 9, 0, 0, 23, 2]

Output: X[ ] = [3, 5, 9, 23, 2, 0, 0, 0]

**Follow-up questions for the interviewer**

**Candidate:** Do we need to maintain the relative order of the elements in the output? Interviewer: Yes, we need to preserve the relative order of the non-zero elements.
**Candidate:** Do we need to solve this problem in place? Interviewer: Yes, we are looking for an O(n) in-place solution.
**Candidate:** Other than zero, are the input values unique? **Interviewer:** No, it can be repeated.

### Discussed solution approaches

- A brute force approach : using extra space and two-loops
- Two pointers in-place solution: using two loops
- Two pointers in-place solution: using a single loop

### A brute force approach : using extra space and two-loops

**Solution Idea**

One basic idea would be to take extra memory of size n and traverse the input array to store all the non-zero elements at the starting indexes of the additional memory. After this, we fill the remaining space of extra memory with zeroes and return it as an output.

This solution will preserve the order of elements, but there are two drawbacks: 1) This is not an in-place solution i.e. we are using extra space to generate the output. 2) We are using two loops to store the output in extra space.

**Solution Steps**

- We declare an extra memory Y[n] to store the output.
- We initialize two-loop pointers: pointer i for traversing the input array X[], and pointer j for storing values in output array Y[].
- Now we run a loop from i = 0 to n - 1 and traverse the input array. When we find a non-zero element X[i], we store it at Y[j] and increment both i and j. Otherwise, we increment the pointer i. By the end of this loop, Y[] stores all the non-zero elements from index 0 to j - 1.
- Finally, we traverse Y[] until j < n and store zeroes at the remaining end part. After this, we return Y[] as an output.

**Solution Pseudocode**

```
int[] moveZeroesEnd(int X[], int n)
{
int Y[n]
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if (X[i] != 0)
{
Y[j] = X[i]
j = j + 1
}
}
while (j < n)
{
Y[j] = 0
j = j + 1
}
return Y
}
```

**Solution Analysis**

Time complexity in the worst case = Time complexity of traversing X[] and storing non-zero elements in Y[] + Time complexity of storing zeroes in Y[] = O(n) + O(n) = O(n). In other words, we are doing a single traversal of both arrays in the worst case. Think!

Space Complexity = O(n), for the extra space Y[].

### Two pointers in-place solution: using two loops

**Solution Idea and Steps**

The critical question is: can we further optimize the above solution to reduce the space complexity or solve the problem In-place? Let’s think!

We can use the above approach, but rather than storing it in extra space, we shift the non-zero elements at the start of the input array itself and fill the remaining part with the zeroes. Here are the steps:

- We traverse the input array using two pointers i and j, where i is for traversing the array and j is for tracking the last index of the non-zero element.
- Whenever we encounter a non-zero element at index i, we shift it to the index j i.e. if (X[i] != 0), X[j] = X[i]. We also increment i and j by 1.
- Otherwise, we ignore the zero and move the pointer i by 1.
- After the above loop, all elements in X[0…j - 1] are non-zero elements. Now, we again traverse X[] from j to n - 1 and fill it with zeroes. Think!

This solution will preserve the order of elements, but there is one drawback: we are using two loops to generate the output.

**Solution Pseudocode**

```
void moveZeroEnd(int X[], int n)
{
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if (X[i] != 0)
{
X[j] = X[i]
j = j + 1
}
}
while (j < n)
{
X[j] = 0
j = j + 1
}
}
```

**Solution Analysis**

Time complexity in the worst case = Time complexity of traversing X[] to shift non-zero elements + Time complexity of traversing X[] to fill zeroes = O(n) + O(n) = O(n). We are solving the problem In-place, so space complexity = O(1)

### Two pointers in-place solution: using a single loop

**Solution idea**

Can we further optimize the above approach and solve it using a single loop? Can we reduce the second traversal to fill the zero at the end? Let's think!

If we observe the intermediate step of the first loop in the above solution, then we can clearly observe a pattern:

- All the elements from 0 to j - 1 would be non-zero.
- All the elements from j to i - 1 would be zero.
- All the elements from i to n - 1 still need to be explored.

So instead of updating X[j] with X[i], if we swap element at index i with index j, then we wouldn’t need to fill the rest of the array with zeroes at the end. All non-zero elements will be moved to the end due to swapping. Think!

Note: this solution idea is similar to the partition process of the quick sort.

**Solution Pseudocode**

```
void moveZeroEnd(int X[], int n)
{
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if(X[i]!= 0)
{
swap(X[j], X[i])
j = j + 1
}
}
}
```

**Solution Analysis**

We are doing only a single traversal where comparison and swapping are the critical operations. Time complexity = O(n), Space complexity = O(1)

**Important Note:** We recommend learners transform the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Please let us know if you find any errors or bugs; we would be highly grateful. Enjoy programming!

### Critical ideas to think!

- Using a similar approach, can we sort an array with only two values repeated? How will we solve this when three values are repeated?
- In the efficient approach, what would be the count of swap operations in the worst-case scenario?
- Can we solve this problem using some other approach? Can we use two pointers moving in the opposite direction?
- Will the above approaches preserve the relative order of non-zero elements?
- Explain the best and worst-case scenarios of all three approaches.
- In the 2nd approach, why are we traversing again to store zeroes to the end of the input array?

### Comparisons of Time and Space Complexities

- Brute force approach : Time = O(n), Space = O(n)
- Two pointers(Two loops): Time = O(n), Space = O(1)
- Two pointers(Single loop): Time = O(n), Space = O(1)

### Suggested coding questions to practice

- Double the first element and move zero to the end
- Segregate even and odd numbers
- Segregate 0s and 1s in an array
- Move all values equal to K to the end of the Array
- The minimum swaps required to sort the array in ascending order

**Enjoy learning, Enjoy coding, Enjoy algorithms!**