Move Zeroes in Array to End

Given an array of integers, your task is to move all the zeroes to the end of the array, while maintaining the relative order of non-zero elements.

This must be done in-place without making a copy of the array, and ideally in a single pass using an optimal approach.

If the array is empty, return it as is.

Understanding the Problem

We are given an array that may contain zero and non-zero numbers. Our goal is to move all the zeroes to the end of the array, while keeping the non-zero elements in their original order.

Importantly, we need to do this in-place, meaning we cannot use another array for storing values temporarily. We must modify the input array directly.

This problem tests both your ability to understand edge cases and write an efficient, space-optimized algorithm.

Step-by-Step with Example

Example Input:

[0, 1, 0, 3, 12]

Step 1: Identify all non-zero elements in the order they appear

We traverse the array and pick up all non-zero values: [1, 3, 12].

Step 2: Place non-zero elements at the beginning

We overwrite the beginning of the array with these values: [1, 3, 12] becomes the first part of the array.

Step 3: Fill the rest of the array with zeroes

After placing non-zero elements, the remaining indices are filled with 0s to complete the array.

Final Result:

[1, 3, 12, 0, 0]

How Do We Handle Edge Cases?

Case 1: No zeroes in the array

If the array is like [1, 2, 3], all elements are non-zero. So, nothing changes and the array remains as is.

Case 2: All elements are zero

Example: [0, 0, 0]. Since there are no non-zero elements to move, the array is already in the required format.

Case 3: Zeros mixed with non-zero elements

This is the general case. Example: [0, 1, 0, 3, 12]. We follow our step-by-step logic to rearrange it to [1, 3, 12, 0, 0].

Case 4: Single element array

If the array has one element (like [0] or [7]), it’s already in the desired state. No changes are needed.

Case 5: Empty array

Example: []. There's nothing to process, so we return the array as is.

Optimal In-Place Approach

Intuition

We use a variable called nonZeroIndex to mark the position where the next non-zero number should go. As we loop through the array, we check each element:

• If it's non-zero, we place it at the nonZeroIndex and move the pointer forward.
• After all non-zero elements are placed, we fill the rest of the array with 0s.

1. Given an array of numbers arr.
2. Initialize a pointer nonZeroIndex to 0.
3. Iterate through each element of the array.
4. If the element is non-zero, assign it to arr[nonZeroIndex] and increment nonZeroIndex.
5. After the loop, fill the rest of the array from nonZeroIndex to the end with zeroes.

Worked example

Let's move all zeroes to the end while maintaining the order of non-zero elements.

Initialize nonZeroIndex = 0. We'll use this to track where the next non-zero element should go.

Check index 0

Element is 0. It's zero. Do nothing and move to next.

Check index 1

Element is 1. It's non-zero, so move it to index 0.

Check index 2

Element is 0. It's zero. Do nothing and move to next.

Check index 3

Element is 3. It's non-zero, so move it to index 1.

Check index 4

Element is 12. It's non-zero, so move it to index 2.

Fill remaining positions with zeroes starting from index 3.

Final Result:

[1,3,12,0,0]

#include <stdio.h>

void moveZeroes(int arr[], int n) {
    int nonZeroIndex = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            arr[nonZeroIndex++] = arr[i];
        }
    }
    while (nonZeroIndex < n) {
        arr[nonZeroIndex++] = 0;
    }
}

int main() {
    int arr[] = {0, 1, 0, 3, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    moveZeroes(arr, n);
    printf("Result: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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

void moveZeroes(vector<int>& arr) {
    int nonZeroIndex = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] != 0) {
            arr[nonZeroIndex++] = arr[i];
        }
    }
    while (nonZeroIndex < arr.size()) {
        arr[nonZeroIndex++] = 0;
    }
}

int main() {
    vector<int> arr = {0, 1, 0, 3, 12};
    moveZeroes(arr);
    cout << "Result: ";
    for (int n : arr) cout << n << " ";
    return 0;
}

def move_zeroes(arr):
    nonZeroIndex = 0
    for i in range(len(arr)):
        if arr[i] != 0:
            arr[nonZeroIndex] = arr[i]
            nonZeroIndex += 1
    for i in range(nonZeroIndex, len(arr)):
        arr[i] = 0
    return arr

arr = [0, 1, 0, 3, 12]
print("Result:", move_zeroes(arr))

public class MoveZeroes {
    public static void moveZeroes(int[] arr) {
        int nonZeroIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                arr[nonZeroIndex++] = arr[i];
            }
        }
        while (nonZeroIndex < arr.length) {
            arr[nonZeroIndex++] = 0;
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 3, 12};
        moveZeroes(arr);
        System.out.print("Result: ");
        for (int num : arr) System.out.print(num + " ");
    }
}

function moveZeroes(arr) {
    let nonZeroIndex = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== 0) {
            arr[nonZeroIndex] = arr[i];
            nonZeroIndex++;
        }
    }
    for (let i = nonZeroIndex; i < arr.length; i++) {
        arr[i] = 0;
    }
    return arr;
}

const arr = [0, 1, 0, 3, 12];
console.log('Result:', moveZeroes(arr));

package main
import "fmt"

func moveZeroes(arr []int) []int {
    nonZeroIndex := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] != 0 {
            arr[nonZeroIndex] = arr[i]
            nonZeroIndex++
        }
    }
    for i := nonZeroIndex; i < len(arr); i++ {
        arr[i] = 0
    }
    return arr
}

func main() {
    arr := []int{0, 1, 0, 3, 12}
    result := moveZeroes(arr)
    fmt.Print("Result: ")
    for _, val := range result {
        fmt.Print(val, " ")
    }
}

fn move_zeroes(arr: &mut Vec<i32>) {
    let mut non_zero_index = 0;
    for i in 0..arr.len() {
        if arr[i] != 0 {
            arr[non_zero_index] = arr[i];
            non_zero_index += 1;
        }
    }
    for i in non_zero_index..arr.len() {
        arr[i] = 0;
    }
}

fn main() {
    let mut arr = vec![0, 1, 0, 3, 12];
    move_zeroes(&mut arr);
    print!("Result: ");
    for n in arr.iter() {
        print!("{} ", n);
    }
}

fun moveZeroes(arr: IntArray) {
    var nonZeroIndex = 0
    for (i in arr.indices) {
        if (arr[i] != 0) {
            arr[nonZeroIndex++] = arr[i]
        }
    }
    while (nonZeroIndex < arr.size) {
        arr[nonZeroIndex++] = 0
    }
}

fun main() {
    val arr = intArrayOf(0, 1, 0, 3, 12)
    moveZeroes(arr)
    print("Result: ")
    for (num in arr) print("$num ")
}

func moveZeroes(_ arr: inout [Int]) {
    var nonZeroIndex = 0
    for i in 0..<arr.count {
        if arr[i] != 0 {
            arr[nonZeroIndex] = arr[i]
            nonZeroIndex += 1
        }
    }
    while nonZeroIndex < arr.count {
        arr[nonZeroIndex] = 0
        nonZeroIndex += 1
    }
}

var arr = [0, 1, 0, 3, 12]
moveZeroes(&arr)
print("Result:", terminator: " ")
for num in arr {
    print(num, terminator: " ")
}

function moveZeroes(arr: number[]): number[] {
    let nonZeroIndex = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== 0) {
            arr[nonZeroIndex] = arr[i];
            nonZeroIndex++;
        }
    }
    for (let i = nonZeroIndex; i < arr.length; i++) {
        arr[i] = 0;
    }
    return arr;
}

const arr: number[] = [0, 1, 0, 3, 12];
console.log('Result:', moveZeroes(arr));

Time complexity

Space complexity

O(1)

The algorithm performs all operations in-place using a constant number of variables, without using any extra space.