Move All Zeroes to the End of an Array

Have you ever cleaned your room and found random items that don’t belong there? Imagine finding toys, books, and clothes scattered everywhere. You decide to organize them by putting all the unwanted items in one corner. This is similar to what we’ll be doing in programming when we need to move all the zeroes in an array to the end.

Think about a motivational story of Marie Kondo, the famous tidying expert. She helps people declutter their homes by finding what’s important and what’s not. In our case, zeroes are like those unwanted items we want to push aside. So, how do we move all zeroes to the end of an array while keeping everything else in order? Let’s explore this together!

Problem statement

You’re given an array of numbers, and your task is to move all the zeroes to the end while maintaining the order of the non-zero elements. The challenge is to do this in an efficient way without creating a new array.

Sample input

1nums = [0, 1, 0, 3, 12]

Sample output

1[1, 3, 12, 0, 0]

Explanation:
In this example, we want to move the zeroes to the end. The non-zero elements [1, 3, 12] remain in the same order, and the zeroes are moved to the end of the array.

Understanding the problem

At first glance, moving zeroes to the end of an array seems simple, but there’s more to it than meets the eye. Imagine trying to sort through a pile of mixed items; you want to keep the important stuff in front and push the less important things to the back. That’s exactly what we’re doing here, except with numbers.

The key challenge is to do this efficiently. We don’t want to create a new array because that would take extra space. Instead, we’ll rearrange the elements within the existing array.

Brute force approach

The simplest way to solve this problem is to loop through the array, find the non-zero elements, and move them to the front while keeping track of the position. After that, we can fill the remaining positions with zeroes. This approach is easy to understand but might not be the most efficient.

Pseudocode

Let’s break down the solution into simple steps that even beginners can follow:

• Initialize a pointer pos at the start of the array.
• Loop through the array with an index i.
• If the current element array[i] is not zero, swap it with the element at array[pos], and then move pos to the next position.
• Continue until you’ve checked all elements.
• The zeroes will naturally be pushed to the end.

Python code

Let’s start with the straightforward approach.

1def move_zeroes_brute_force(array):
2    result = [num for num in array if num != 0]
3    result += [0] * (len(array) - len(result))
4    return result

Explanation

• We create a new list result that includes all non-zero elements.
• Then, we add the necessary number of zeroes to the end of result.
• Finally, we return result.

Java code

1import java.util.ArrayList;
2import java.util.List;
3
4public class MoveZeroes {
5    public static int[] moveZeroesBruteForce(int[] array) {
6        List<Integer> resultList = new ArrayList<>();
7        for (int num : array) {
8            if (num != 0) {
9                resultList.add(num);
10            }
11        }
12        while (resultList.size() < array.length) {
13            resultList.add(0);
14        }
15        return resultList.stream().mapToInt(i -> i).toArray();
16    }
17}

C++ code

1#include <vector>
2
3std::vector<int> moveZeroesBruteForce(const std::vector<int>& array) {
4    std::vector<int> result;
5    for (int num : array) {
6        if (num != 0) {
7            result.push_back(num);
8        }
9    }
10    while (result.size() < array.size()) {
11        result.push_back(0);
12    }
13    return result;
14}

Explanation

• The brute force approach creates a new array or list to store the non-zero elements.
• We then add zeroes to the end to match the original array’s length.
• This method uses extra space and might not be the best for large arrays.

A smarter approach

A more efficient way is to use two pointers: one for iterating through the array and another for tracking the position of the next non-zero element. By swapping elements in place, we can move all zeroes to the end without needing additional space.

Smart approach using two pointers

Now, let’s improve the solution using the two-pointer technique.

Python code

1def move_zeroes(array):
2    pos = 0
3    for i in range(len(array)):
4        if array[i] != 0:
5            array[pos], array[i] = array[i], array[pos]
6            pos += 1
7    return array

Explanation

• pos is a pointer that tracks the position of the next non-zero element.
• We iterate through the array with i, and whenever we find a non-zero element, we swap it with the element at pos.
• This ensures all non-zero elements are at the front, and zeroes naturally move to the end.

Java code

1public class MoveZeroes {
2    public static void moveZeroes(int[] array) {
3        int pos = 0;
4        for (int i = 0; i < array.length; i++) {
5            if (array[i] != 0) {
6                int temp = array[pos];
7                array[pos] = array[i];
8                array[i] = temp;
9                pos++;
10            }
11        }
12    }
13}

C++ code

1#include <vector>
2
3void moveZeroes(std::vector<int>& array) {
4    int pos = 0;
5    for (int i = 0; i < array.size(); i++) {
6        if (array[i] != 0) {
7            std::swap(array[pos], array[i]);
8            pos++;
9        }
10    }
11}

Explanation

• The logic is the same in Python, Java, and C++.
• We use a pointer pos to keep track of where the next non-zero element should go.
• As we iterate through the array, we swap elements in place to move all zeroes to the end.
• This approach is efficient with a time complexity of O(n) and uses no extra space.

Conclusion

Moving all zeroes to the end of an array is a common problem that teaches us the importance of efficiency in programming. While the brute force approach is easy to understand, it uses extra space and isn’t the most efficient. The two-pointer technique, on the other hand, offers a smart and efficient way to solve the problem without using additional space.

Just like Marie Kondo helps people declutter their homes by organizing what’s important and what’s not, this problem helps us think about organizing data in a more efficient way. By mastering these techniques, you’ll be better prepared to tackle similar problems in the future.