Difficulty: Easy, Asked-in: Facebook, Amazon, Uber, LinkedIn, Bloomberg
Key-takeaway: An excellent problem to learn problem-solving using single loop and two pointers approach. In two-pointers approach, both pointers are moving in the same direction.
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]
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 extra memory space with zeroes.
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 use two loops to store the output in extra space.
int[] moveZeroesEnd(int X[], int n)
{
int output[n]
int j = 0
for (int i = 0; i < n; i = i + 1)
{
if (X[i] != 0)
{
output[j] = X[i]
j = j + 1
}
}
while (j < n)
{
output[j] = 0
j = j + 1
}
return output
}
def moveZeroesEnd(X: List[int]) -> List[int]:
n = len(X)
output = [0] * n
j = 0
for i, x in enumerate(X):
if x != 0:
output[j] = x
j = j + 1
return output
Time complexity in the worst case = Time complexity of traversing X[] and storing non-zero elements in output[] + Time complexity of storing zeroes in output[] = 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 extra space output[].
The critical question is: Can we further optimize the space complexity of the above solution and solve the problem in place? Let’s think!
We can use the idea of above approach, but rather than storing output 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:
This solution will preserve the order of elements, but there is one drawback: We are using two loops to generate the output.
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
}
}
def moveZeroesEnd(X, n):
j = 0
for i in range(n):
if X[i] != 0:
X[j] = X[i]
j = j + 1
while j < len(X):
X[j] = 0
j = j + 1
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).
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 observe a pattern:
So, when the element at X[i] is non-zero, instead of updating X[j] with X[i], if we swap the 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.
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
}
}
}
def moveZeroEnd(X, n):
j = 0
for i in range(n):
if X[i] != 0:
X[i], X[j] = X[j], X[i]
j = j + 1
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;
}
}
}
We are doing only a single traversal where comparison and swapping are 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!
Enjoy learning, Enjoy coding, Enjoy algorithms!