Move Zeroes in Array to End using Loop - Optimal Algorithm

Visualization Player

Problem Statement

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.

Examples

Input Array Output Array Description
[0, 1, 0, 3, 12] [1, 3, 12, 0, 0] All non-zero elements kept in order, zeroes pushed to the endVisualization
[1, 2, 3] [1, 2, 3] No zeroes present, array remains unchangedVisualization
[0, 0, 0] [0, 0, 0] All elements are zeroes, no changes neededVisualization
[4, 0, 5, 0, 6] [4, 5, 6, 0, 0] Zeroes moved to end, non-zero order maintainedVisualization
[] [] Empty array, returns emptyVisualization
[0] [0] Single element which is zeroVisualization
[9] [9] Single non-zero element, unchangedVisualization
[0, 1, 0, 2, 0, 3] [1, 2, 3, 0, 0, 0] Multiple interleaved zeroes correctly pushed to the endVisualization

Solution

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.

Algorithm Steps

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)Even if no zeros are present, the algorithm still iterates through the entire array once to check each element.
Average CaseO(n)The algorithm goes through the array once to move non-zero elements and then fills the remaining positions with zeroes.
Worst CaseO(n)When all elements are zero or all are non-zero, the algorithm still performs a full scan and update in two linear passes.

Space Complexity

O(1)

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

Detailed Step by Step Example

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

{ "array": [0,1,0,3,12], "showIndices": true }

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.

{ "array": [0,1,0,3,12], "showIndices": true, "highlightIndices": [0], "labels": { "0": "i", "-1": "nonZeroIndex" } }

Check index 1

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

{ "array": [1,1,0,3,12], "showIndices": true, "highlightIndices": [1], "labels": { "1": "i", "0": "nonZeroIndex" } }

Check index 2

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

{ "array": [1,1,0,3,12], "showIndices": true, "highlightIndices": [2], "labels": { "2": "i", "0": "nonZeroIndex" } }

Check index 3

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

{ "array": [1,3,0,3,12], "showIndices": true, "highlightIndices": [3], "labels": { "3": "i", "1": "nonZeroIndex" } }

Check index 4

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

{ "array": [1,3,12,3,12], "showIndices": true, "highlightIndices": [4], "labels": { "4": "i", "2": "nonZeroIndex" } }

Fill remaining positions with zeroes starting from index 3.

{ "array": [1,3,12,0,0], "showIndices": true, "labels": { "3": "start filling 0s" } }

Final Result:

[1,3,12,0,0]


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...