Tag move zeros

Move All Zeros to End of Array in C: A Comprehensive Tutorial

Moving all zeros to the end of an array while maintaining the relative order of non-zero elements is a classic array manipulation problem. It tests your understanding of in-place operations, two-pointer techniques, and time-space trade-offs. This problem appears frequently in coding interviews and has practical applications in data compaction and memory management.

This tutorial provides an in-depth exploration of moving zeros to the end in C: naive temporary array approach, two-traversal method, one-traversal swap approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array of integers, rearrange it so that all zeros appear at the end while non-zero elements maintain their original relative order.

Example:

text

Input: [1, 2, 0, 4, 3, 0, 5, 0] Output: [1, 2, 4, 3, 5, 0, 0, 0]

Why This Problem Matters

• In-place manipulation: Teaches efficient array transformation.
• Two-pointer technique: Foundation for many array algorithms.
• Stable partitioning: Maintains relative order of elements.
• Real-world applications: Data compaction, memory defragmentation.
• Interview preparation: Very common coding interview question.

Key Insight

Use a “write pointer” (count) to track where the next non-zero element should be placed. As we scan the array, non-zero elements are moved to the front, and zeros naturally end up at the back.

Approaches Overview

Approach	Time	Space	Traversals
Temporary array	O(n)	O(n)	3
Two traversals	O(n)	O(1)	2
One traversal (swap)	O(n)	O(1)	1

---

Syntax & Core Mechanics

Approach 1: Temporary Array (Naive)

Copy non-zero elements to a temporary array, fill the rest with zeros, then copy back.

c

#include <stdio.h> #include <stdlib.h> void pushZerosToEndTemp(int arr[], int n) { if (n <= 1) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } int j = 0; /* Copy non-zero elements to temp */ for (int i = 0; i < n; i++) { if (arr[i] != 0) { temp[j++] = arr[i]; } } /* Fill remaining with zeros */ while (j < n) { temp[j++] = 0; } /* Copy back */ for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } int main(void) { int arr[] = {1, 2, 0, 4, 3, 0, 5, 0}; int n = sizeof(arr) / sizeof(arr[0]); pushZerosToEndTemp(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

1 2 4 3 5 0 0 0

Time: O(n), Space: O(n)

Approach 2: Two Traversals (In-Place)

Use a count pointer; copy non-zero elements to the front, then fill the rest with zeros.

c

#include <stdio.h> void pushZerosToEndTwoPass(int arr[], int n) { if (n <= 1) return; int count = 0; /* Move non-zero elements to the front */ for (int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; } } /* Fill remaining positions with zeros */ while (count < n) { arr[count++] = 0; } } int main(void) { int arr[] = {1, 2, 0, 4, 3, 0, 5, 0}; int n = sizeof(arr) / sizeof(arr[0]); pushZerosToEndTwoPass(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

1 2 4 3 5 0 0 0

Time: O(n), Space: O(1), Traversals: 2

Approach 3: One Traversal (Swap) — Optimal

Swap non-zero elements with the element at count, pushing zeros toward the end.

c

#include <stdio.h> void pushZerosToEnd(int arr[], int n) { if (n <= 1) return; int count = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { /* Swap arr[i] with arr[count] */ int temp = arr[i]; arr[i] = arr[count]; arr[count] = temp; count++; } } } int main(void) { int arr[] = {1, 2, 0, 4, 3, 0, 5, 0}; int n = sizeof(arr) / sizeof(arr[0]); pushZerosToEnd(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

1 2 4 3 5 0 0 0

Time: O(n), Space: O(1), Traversals: 1

How it works:

• count tracks the position where the next non-zero element should go.
• When a non-zero is found, swap it with arr[count].
• If arr[count] was 0, the zero moves to position i (later swapped forward again if needed).
• Non-zero elements retain their relative order.

---

Full Practical Code Example with Explanation

This program demonstrates all three approaches with verification, performance comparison, and edge cases.

Program: Move Zeros to End Comparison

c

/** * move_zeros_to_end.c * Demonstrates multiple approaches to move zeros to the end of an array. * Includes verification, timing, and edge case handling. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ void pushZerosTemp(int arr[], int n); void pushZerosTwoPass(int arr[], int n); void pushZerosOnePass(int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); int arraysEqual(const int a[], const int b[], int n); void copyArray(const int src[], int dst[], int n); int verifyResult(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Move Zeros to End Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nOriginal: "); printArray(arr, n); int *copy = malloc(n * sizeof(int)); if (copy == NULL) break; copyArray(arr, copy, n); pushZerosTemp(copy, n); printf("Temp Array: "); printArray(copy, n); copyArray(arr, copy, n); pushZerosTwoPass(copy, n); printf("Two Pass: "); printArray(copy, n); copyArray(arr, copy, n); pushZerosOnePass(copy, n); printf("One Pass: "); printArray(copy, n); free(copy); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Approach 1: Temporary array */ void pushZerosTemp(int arr[], int n) { if (n <= 1) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } int j = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { temp[j++] = arr[i]; } } while (j < n) { temp[j++] = 0; } for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } /* Approach 2: Two traversals */ void pushZerosTwoPass(int arr[], int n) { if (n <= 1) return; int count = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; } } while (count < n) { arr[count++] = 0; } } /* Approach 3: One traversal with swap */ void pushZerosOnePass(int arr[], int n) { if (n <= 1) return; int count = 0; for (int i = 0; i < n; i++) { if (arr[i] != 0) { int temp = arr[i]; arr[i] = arr[count]; arr[count] = temp; count++; } } } /* Verifies that all zeros are at end and non-zeros retain order */ int verifyResult(const int arr[], int n) { int seenZero = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) { seenZero = 1; } else if (seenZero) { return 0; /* Non-zero after zero: invalid */ } } return 1; } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Compares arrays */ int arraysEqual(const int a[], const int b[], int n) { for (int i = 0; i < n; i++) { if (a[i] != b[i]) return 0; } return 1; } /* Copies array */ void copyArray(const int src[], int dst[], int n) { memcpy(dst, src, n * sizeof(int)); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== All Approaches ===\n"); int original[] = {1, 2, 0, 4, 3, 0, 5, 0}; int n = sizeof(original) / sizeof(original[0]); int expected[] = {1, 2, 4, 3, 5, 0, 0, 0}; int arr[MAX_SIZE]; printf("Original: [1, 2, 0, 4, 3, 0, 5, 0]\n"); printf("Expected: [1, 2, 4, 3, 5, 0, 0, 0]\n\n"); copyArray(original, arr, n); pushZerosTemp(arr, n); printf("Temp Array: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); pushZerosTwoPass(arr, n); printf("Two Pass: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); pushZerosOnePass(arr, n); printf("One Pass: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int size = 100000; int *original = malloc(size * sizeof(int)); int *arr = malloc(size * sizeof(int)); if (original == NULL || arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(original); free(arr); return; } /* Fill with half zeros, half non-zeros */ for (int i = 0; i < size; i++) { original[i] = (i % 2 == 0) ? 0 : (i + 1); } clock_t start, end; double timeTaken; /* Temp approach */ copyArray(original, arr, size); start = clock(); pushZerosTemp(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Temp Array: %.3f ms\n", timeTaken); /* Two pass */ copyArray(original, arr, size); start = clock(); pushZerosTwoPass(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Two Pass: %.3f ms\n", timeTaken); /* One pass */ copyArray(original, arr, size); start = clock(); pushZerosOnePass(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("One Pass: %.3f ms\n", timeTaken); free(original); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: No zeros */ int arr1[] = {10, 20, 30}; printf("Case 1: No zeros\n"); printf(" Before: "); printArray(arr1, 3); pushZerosOnePass(arr1, 3); printf(" After: "); printArray(arr1, 3); /* Case 2: All zeros */ int arr2[] = {0, 0, 0}; printf("\nCase 2: All zeros\n"); printf(" Before: "); printArray(arr2, 3); pushZerosOnePass(arr2, 3); printf(" After: "); printArray(arr2, 3); /* Case 3: Single element (zero) */ int arr3[] = {0}; printf("\nCase 3: Single zero\n"); printf(" Before: "); printArray(arr3, 1); pushZerosOnePass(arr3, 1); printf(" After: "); printArray(arr3, 1); /* Case 4: Single element (non-zero) */ int arr4[] = {5}; printf("\nCase 4: Single non-zero\n"); printf(" Before: "); printArray(arr4, 1); pushZerosOnePass(arr4, 1); printf(" After: "); printArray(arr4, 1); /* Case 5: Zeros at beginning */ int arr5[] = {0, 0, 1, 2, 3}; printf("\nCase 5: Zeros at beginning\n"); printf(" Before: "); printArray(arr5, 5); pushZerosOnePass(arr5, 5); printf(" After: "); printArray(arr5, 5); /* Case 6: Zeros at end (already correct) */ int arr6[] = {1, 2, 3, 0, 0}; printf("\nCase 6: Zeros already at end\n"); printf(" Before: "); printArray(arr6, 5); pushZerosOnePass(arr6, 5); printf(" After: "); printArray(arr6, 5); /* Case 7: Negative numbers */ int arr7[] = {-1, 0, -2, 0, -3}; printf("\nCase 7: Negative numbers\n"); printf(" Before: "); printArray(arr7, 5); pushZerosOnePass(arr7, 5); printf(" After: "); printArray(arr7, 5); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Temp Array: Simple, but uses O(n) extra space.
2. Two Pass: In-place, O(1) space, two traversals.
3. One Pass: In-place, O(1) space, single traversal with swaps — most efficient.

Expected Output (sample run)

text

=== Move Zeros to End Demo === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === All Approaches === Original: [1, 2, 0, 4, 3, 0, 5, 0] Expected: [1, 2, 4, 3, 5, 0, 0, 0] Temp Array: [1, 2, 4, 3, 5, 0, 0, 0] Verify: PASS Two Pass: [1, 2, 4, 3, 5, 0, 0, 0] Verify: PASS One Pass: [1, 2, 4, 3, 5, 0, 0, 0] Verify: PASS --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000) === Temp Array: 1.234 ms Two Pass: 0.512 ms One Pass: 0.487 ms --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: No zeros Before: [10, 20, 30] After: [10, 20, 30] Case 2: All zeros Before: [0, 0, 0] After: [0, 0, 0] Case 3: Single zero Before: [0] After: [0] Case 4: Single non-zero Before: [5] After: [5] Case 5: Zeros at beginning Before: [0, 0, 1, 2, 3] After: [1, 2, 3, 0, 0] Case 6: Zeros already at end Before: [1, 2, 3, 0, 0] After: [1, 2, 3, 0, 0] Case 7: Negative numbers Before: [-1, 0, -2, 0, -3] After: [-1, -2, -3, 0, 0]

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Losing Relative Order of Non-Zeros

Using an unstable partition (e.g., sorting or certain swap patterns) destroys the original order.

c

/* Wrong: swaps first non-zero with last, changing order */

Solution: Use the count-based approach that preserves order.

2. Overwriting Non-Zeros in Two-Pass

In two-pass, overwriting with arr[count++] = arr[i] is safe because count <= i always.

c

for (int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; /* Safe: count <= i */ } }

3. Forgetting to Fill Zeros

In two-pass, forgetting to fill remaining positions with zeros.

c

while (count < n) { arr[count++] = 0; /* Required */ }

4. Empty Array

Handle n <= 0 before processing.

c

if (n <= 1) return;

5. Single Element

A single element is trivially correct.

c

int arr[] = {0}; /* Already correct */

6. All Zeros

All-zero arrays remain unchanged.

c

int arr[] = {0, 0, 0};

7. No Zeros

Arrays without zeros remain unchanged.

c

int arr[] = {1, 2, 3};

8. Memory Leaks with Temp Array

Forgetting to free the temporary array.

c

int *temp = malloc(n * sizeof(int)); /* ... */ free(temp); /* Required */

9. Integer Overflow in count

Using int for count is fine for typical arrays; use size_t for very large arrays.

10. Memory Considerations

• Temp Array: O(n) extra space.
• Two Pass: O(1) extra space.
• One Pass: O(1) extra space; preferred for memory efficiency.
• No dynamic allocation in in-place approaches.

---

Summary & Best Practices

Moving all zeros to the end of an array is a fundamental in-place array manipulation problem. The one-pass swap approach is the most efficient, using O(n) time and O(1) space.

Key Takeaways

• Maintain relative order of non-zero elements.
• Use a count pointer to track the next non-zero position.
• Temp array: O(n) time, O(n) space.
• Two pass: O(n) time, O(1) space, two traversals.
• One pass: O(n) time, O(1) space, single traversal with swaps.

Best Practices

1. Use the one-pass swap approach for optimal efficiency.
2. Preserve relative order of non-zero elements.
3. Handle edge cases: empty, single element, all zeros, no zeros.
4. Free dynamically allocated memory in the temp approach.
5. Use size_t for very large arrays.
6. Verify results with a helper function during testing.
7. Validate input (array size, values).
8. Document the approach with comments.
9. Test with negative numbers and mixed values.
10. Profile performance for large arrays.

By mastering this problem, you’ll understand the two-pointer technique and be prepared for related problems like removing duplicates, partitioning arrays, and stable sorting.