Write A C Program To Move All Zeros To The End Of An Array – Two Pointer Technique Solution

Write a c program to move all zeros to the end of an array is an interview question asked by most giant tech companies which i will use the two pointer technique to show you how to solve it with accepted time and space complexity.

Problem Statement

Given an array arr write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

You must do this in-place without creating a copy of the array

Example input 1

arr[] = {12,400,0,0,1,1,0,0}

output: arr[] = {12,400,1,1,0,0,0,0}

Hint

  • We can use two pointers to solve this problem; one pointer to iterate the array (call it i) and the other to point to the new array length (call it newLength), both pointers start from index 0;
  • Iterate the whole array one element at a time using pointer i and if each array index value is not equal to 0, place that value in the newlength index and increment newlength index otherwise if the array index value is equal to 0, just move pointer i to the next element and continue the process.

For our given input for example,

  • Get start value of pointer i index i.e 12
  • Compare the value of pointer i index (i.e 12) to 0, value is not 0, re-assign 12 to pointer i and increment pointer newlength by 1.
  • Next we retrieve pointer i value which is now 400 and compare with 0, they are not the same so again we re-assign 400 to pointer i and increment pointer newlength by 1
  • Next we retrieve pointer i value which is now 0 and compare with 0, they are same, we just skip this and move pointer i to next index
  • Again we compare the value of pointer i to 0 and still find them to be same, again move pointer i to next index
  • Now we arrive at an index where its value is 1, compare with 0, they are not the same so we assign 1 to the newlength pointer index as it value and increment newlength by 1
  • Now continue this steps and you find that at the end of the day what you have is arr[] = {12,400,1,1,1,1,0,0}, but you see there were 4 0’s not 2; so what you do, from the newlength pointer just change all the indices values that are not zero to zero.

So now your array should look like this

The Solution

This is code written in c but you can use same algorithm to write it in whatever language you choose to.

#include <stdio.h>

int moveZeroes(int *arr, int n)
{
    int i, newlength = 0;
    
    for(i=0; i<n; i++)
        if(arr[i] != 0)
            arr[newlength++] = arr[i];
            
    for(i=newlength; i<n; i++)
        if(arr[i] != 0)
            arr[i] = 0;
            
    return 0;
}

int main()
{
    int ary[8] = {12,400,0,0,1,1,0,0};
    int i;
    int sz = sizeof(ary)/sizeof(ary[0]);
    moveZeroes(ary, sz);
    for(i=0; i<sz; i++)
         printf("Ary[%d] = %d\n", i, ary[i]);
}

OUTPUT

Also see more detailed output in leetcode though with a different input.

Time and Space Complexity Analysis

  • Time complexity is O(n); i.e the algorithm runs in linear time
  • Space complexity is O(1)

Conclusion

The two pointer technique algorithm used to write a C program to move all zeros to the end of an array is accepted by leetcode; please see status in attached image, and notice that the algorithm runs at 12ms for the given input and is faster than 93.13% of other codes submitted in c for this particular problem statement and the memory usage is 7.6 MB which is 82.12% less than the memory of other codes submitted for this problem.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like