Move all zeros to the end of an array

by

1. What Does This Problem Ask?

The problem “move all zeros to end of array” is a classic in-place array manipulation challenge. You are given an array of integers that contains a mix of zeros and non-zero values. Your goal is to rearrange the array so that:

  • All zeros are pushed to the end of the array.
  • All non-zero elements retain their original relative order.
  • The operation is done in-place — no additional array is used.

This problem tests your understanding of the two-pointer technique, a fundamental pattern in array and string problems. It frequently appears in placement tests at companies like Amazon, Google, Flipkart, and TCS, making it essential for any serious DSA preparation.

2. Problem Statement

Given an array of integers arr[] of size n, move all zeros to end of array while maintaining the relative order of all non-zero elements. The solution must operate in-place without using an extra array.

⚡Key Constraint: In-place modification only. No extra array. Relative order of non-zero elements must be preserved.

Visual Example

Input array (zeros scattered throughout):

Non-zero elements 1, 3, 12 maintain their original order. Zeros are pushed to the end.

3. Approach

How to Move All Zeros to End of Array – The Algorithm

The most efficient way to move all zeros to end of array is the two-pointer (swap) technique. We maintain one pointer j that always points to the next available position for a non-zero element, and a second pointer i that scans through the array.

Step-by-Step Algorithm

  1. Initialize pointer j = 0. This tracks where the next non-zero element should be placed.
  2. Iterate through the array with pointer i from index 0 to n-1.
  3. When arr[i] != 0, swap arr[i] with arr[j] and increment j.
  4. If arr[i] == 0, skip — do nothing, let i advance naturally.
  5. After the loop ends, all non-zeros are at the front in original order, and zeros have been pushed to the end.
💡Why swap and not shift? Swapping is O(1) per step and avoids the O(n²) cost of repeated shifting. This is what makes the two-pointer approach optimal for moving zeros to the end of an array.

4. Flowchart – Move All Zeros to End of Array

5. Pseudocode

START
  READ n
  READ array[0..n-1]

  SET j = 0

  FOR i FROM 0 TO n-1:
    IF array[i] != 0:
      SWAP array[i] AND array[j]
      j = j + 1

  PRINT array
END

6.Python Solution – Move All Zeros to End of Array


n = int(input())
arr = list(map(int, input().split()))

j = 0

for i in range(len(arr)):
    if arr[i] != 0:
        arr[i], arr[j] = arr[j], arr[i]
        j += 1

print(*arr)

7. Explanation

1. Reading Input

n = int(input()) reads the total count of elements. arr = list(map(int, input().split())) reads space-separated integers on the next line and converts them into a Python list.

Example: Input 5 → 0 1 0 3 12 produces arr = [0, 1, 0, 3, 12].

2. The Two-Pointer Variable

j = 0 initializes a pointer that always indicates the next empty slot for a non-zero value. As we find non-zero elements, j advances, effectively filling positions from the front.

3. The Core Loop

We iterate i over every index. When arr[i] != 0, we swap arr[i] with arr[j] and increment j. This pulls the non-zero element to its correct position. Zeros naturally accumulate at positions j and beyond as non-zeros are swapped forward.

4. Printing the Result

print(*arr) uses Python’s unpacking operator to print all array elements separated by spaces — exactly the expected output format.

8. Step-by-Step Dry Run

Input: arr = [0, 1, 0, 3, 12], n = 5, initial j = 0

i arr[i] Condition Action Array State j after
0 0 arr[0] == 0 Skip [0, 1, 0, 3, 12] 0
1 1 arr[1] != 0 Swap i=1, j=0 [1, 0, 0, 3, 12] 1
2 0 arr[2] == 0 Skip [1, 0, 0, 3, 12] 1
3 3 arr[3] != 0 Swap i=3, j=1 [1, 3, 0, 0, 12] 2
4 12 arr[4] != 0 Swap i=4, j=2 [1, 3, 12, 0, 0] 3

Final Output: 1 3 12 0 0 — all zeros moved to the end, non-zero order preserved. ✅

9. Complexity

O(n)
Time Complexity

We traverse the array exactly once. Each element is visited one time regardless of input size.

O(1)
Space Complexity

No extra array is used. Only two pointers i and j are maintained — constant space.

Why Is This Optimal?

To move all zeros to end of array, we must at minimum read every element once — which already requires O(n). Our solution achieves this lower bound exactly. No sorting (O(n log n)), no extra pass, no auxiliary array. This makes it the theoretically optimal solution for this problem.

A naive approach using an extra array would cost O(n) space — acceptable but wasteful. The two-pointer swap approach described here is strictly superior.

10. Test Cases – Move Zeros to End of Array

Case 1 · Basic Mixed
Zeros scattered in input
Input
5
0 1 0 3 12
Output
1 3 12 0 0
Case 2 · No Zeros
Array has no zeros at all
Input
4
1 2 3 4
Output
1 2 3 4
Case 3 · All Zeros
Every element is zero
Input
4
0 0 0 0
Output
0 0 0 0
Case 4 · Single Element
Edge case: n = 1
Input
1
0
Output
0
Case 5 · Large Mixed Array
Multiple zeros interspersed
Input
6
4 0 5 0 0 3
Output
4 5 3 0 0 0

10 · Interview

11. Interview Tips for Move All Zeros to End of Array

  • 🎯Clarify constraints first. Ask if negative numbers are possible, if the array can be empty, and whether in-place is strictly required. Interviewers reward candidates who think about edge cases before coding.
  • 🔄Mention the two approaches. The brute force (extra array, O(n) space) vs. the optimal two-pointer swap (O(1) space). Always prefer the in-place approach and explain why — it shows you understand memory constraints.
  • 🧪Test edge cases out loud. Walk through “all zeros”, “no zeros”, and “single element” cases before submitting. This demonstrates systematic thinking — a quality every interviewer values.
  • ⚡State complexity explicitly. Say “This runs in O(n) time and O(1) space.” Interviewers at top companies expect candidates to volunteer this information without being prompted.
  • 🔗Connect to related problems. This exact two-pointer pattern is used in “Sort Colors” (Dutch National Flag), “Remove Duplicates from Sorted Array”, and “Partition Array”. Mentioning this shows depth of understanding.

 

Leave a Comment