What is the moving zeroes problem?
Problem statement
This shot will discuss an interesting coding interview question called "moving zeroes". The problem statement is as follows:
You are given an array of integers nums. Your task is to move all the 0s to the end of the array. While moving the 0s, you have to ensure that the relative order of the non-zero elements is not changed. Another constraint to the problem is that the space complexity of your solution should be O(1). This means that you need to move the 0s in-place without creating an extra array.
Let us try to understand the problem with the help of an example. Suppose that we are given an array [0, 1, 0, 3, 12]. Our solution should return an array after moving all the 0s to the end and maintaining the order of all the non-zero elements. The final array should look like [1, 3, 12, 0, 0].
Solution approach
Let's now discuss the solution approach for the given problem. We will follow the steps mentioned below to solve the problem.
- First, we will create two pointers that point to the array’s first element.
- Then, the first pointer will traverse all the elements of the array. As soon as we encounter a non-zero element in the array, we will swap the two elements, namely the non-zero element and the element being pointed to by the second pointer. After the swapping is performed, we will need to increment the second pointer as it will then point to the first
0th element in the array. - Once our first pointer reaches the end of the array, all the
0s would have been moved to the end while the relative order of the non-zero elements would also have been maintained.
Let's understand the above solution approach with some illustrations given below.
Code
Let's now look at the code for this solution.
#include <bits/stdc++.h>using namespace std;// Function to move all the zeroes to the endvoid moveZeroes(vector<int>& nums) {for(int i = 0, j = 0; j < nums.size(); j++){if (nums[j] != 0){swap(nums[i], nums[j]);i++; //incrementing the second pointer as there was swapping performed}}}int main() {vector<int> vec = {0, 1, 0, 3, 12};cout << "Original vector:\n";for(int v : vec)cout << v << " ";cout << "\nVector after moving all the zeroes to the end:\n";moveZeroes(vec);for(int v : vec)cout << v << " ";}
Explanation
- In lines 5–12, we create a function
moveZeroes()that accepts the vector by reference. Whatever changes we make in the vector will be reflected in the original vector. - In line 16, we create a vector of integers.
- In lines 19–20, we print the elements of the vector.
- In line 23, we call the function
moveZeroes()to move all the0s to the end of the vector. - Finally, in lines 24–25, we print the updated vector. It can be observed that all the
0s are moved to the end of the vector without creating an extra array.