Moving Zeros to the End of an Array: A Comprehensive Guide

In programming, efficiently manipulating arrays is a common challenge. One such task is moving all zeros to the end of an array while maintaining the order of non-zero elements. In this blog, we’ll discuss two approaches to solve this problem, compare their implementations, and explore ways to optimize them.

---

The Problem Statement

Given an integer array, modify it in place to move all zero elements to the end while maintaining the relative order of the non-zero elements.

Example:

Input:
[0, 1, 0, 3, 12]

Output:
[1, 3, 12, 0, 0]

---

Approach 1: Basic Implementation

Code:

void pushZerosToEnd(int[] arr) {
    int count = 0; // Tracks the index to place the next non-zero element
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != 0) {
            int temp = arr[i];
            arr[i] = arr[count];
            arr[count] = temp;
            count++;
        }
    }
}

Logic:

1. Use a variable count to track the position where the next non-zero element should go.

2. Iterate through the array:

   • If the current element is non-zero:

     • Swap it with the element at the count index.

     • Increment count to the next position.

Time Complexity:

• O(n): We traverse the array once.

• Swapping is a constant-time operation.

Space Complexity:

• O(1): The array is modified in place without using additional memory.

---

Approach 2: Enhanced Readability with Comments

Code:

static void pushZerosToEnd(int[] arr) {
    int count = 0; // Pointer for the position of the next non-zero element
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != 0) {
            // Swap only if necessary
            int temp = arr[i];
            arr[i] = arr[count];
            arr[count] = temp;
            count++;
        }
    }
}

What’s Different?

• This version includes comments, explaining each step of the logic, making it beginner-friendly and easier to understand.

• However, the logic remains identical to the first approach.

---

Observations and Shortcomings of Both Approaches:

1. Unnecessary Swaps:

   • The functions swap elements even when the current element is already in its correct position (when i == count).

   • This results in redundant operations.

2. Clarity vs. Performance:

   • While the second version is more readable, neither approach minimizes swaps.

---

Optimized Approach

To address these inefficiencies, we can modify the code to avoid unnecessary swaps:

Optimized Code:

static void pushZerosToEnd(int[] arr) {
    int count = 0; // Tracks the position for the next non-zero element

    for (int i = 0; i < arr.length; i++) {
        // If the current element is non-zero
        if (arr[i] != 0) {
            // Swap only if the indices are different
            if (i != count) {
                arr[count] = arr[i];
                arr[i] = 0; // Move zero to the current index
            }
            count++;
        }
    }
}

Improvements:

1. Avoid Redundant Swaps:

   • The condition if (i != count) ensures swapping occurs only when necessary, reducing computation.

2. Same Time Complexity:

   • O(n): The loop still runs once over the array.

3. Same Space Complexity:

   • O(1): No additional data structures are used.

Explanation:

• count acts as a pointer to track the next position for a non-zero element.

• If arr[i] is non-zero and i != count, we swap arr[i] with arr[count]. This ensures that each element is moved only when necessary.

---

Comparison of the Approaches

---

Approach 3: Leveraging C++ STL Functions

C++ provides powerful Standard Template Library (STL) functions that simplify common operations. One such function is stable_partition.

Code:

#include <vector>
#include <algorithm>
using namespace std;

void pushZerosToEnd(vector<int>& arr) {
    stable_partition(arr.begin(), arr.end(), [](int n) { 
        return n != 0; 
    });
}

How It Works:

1. stable_partition rearranges elements in the container such that elements satisfying the condition appear before those that don't, while maintaining their relative order.

2. The lambda function [](int n) { return n != 0; } ensures non-zero elements are moved to the front.

Time Complexity:

• O(n): The stable_partition algorithm processes each element once.

Space Complexity:

• O(1): Operates in place without additional memory.

---

Why Use C++ STL for This Problem?

1. Simplicity:

   • The use of stable_partition reduces the code to a single line, making it highly readable.

2. Efficiency:

   • STL algorithms are optimized for performance, ensuring minimal overhead.

3. Maintainability:

   • Using standard functions improves maintainability and reduces the risk of bugs.

---

Comparing the Approaches

Practical Insights

1. When to Use Which Approach?

   • If readability is the top priority (e.g., for teaching purposes), the enhanced implementation is a good choice.

   • For production code, the optimized implementation is better due to reduced redundant operations.

2. General Tip for Array Manipulation:

   • Always consider edge cases like empty arrays or arrays with no zeros.

3. Further Optimization:

   • If the array contains a large number of zeros, minimizing swaps can significantly improve performance.

---

Conclusion

We explored multiple ways to solve the problem of moving zeros to the end of an array, starting from a basic implementation to an optimized solution. While all approaches achieve the desired result, the optimized version stands out by reducing unnecessary operations, making it more efficient. This example highlights the importance of refining algorithms for better performance, especially when dealing with large datasets.

Mastering such techniques is essential for both interview preparation and real-world applications. Keep practicing, and happy coding! 🎉