Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

leetcode
interview
c++
communitycreator

What is the moving zeroes problem?

Harsh Jain

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

Pointer 'j' pointing to 0
1 of 7

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 end
void 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 << " ";
}
Move zeroes

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 the 0s 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.

RELATED TAGS

leetcode
interview
c++
communitycreator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring