Move 0's to end of array

Question

I need to move all 0's in an array to the end of the array.

Example: [1, 10, 0, 5, 7] should result in [1, 10, 5, 7, 0].

I am open to doing a reverse loop or a regular loop.

I cannot create a new array.

Here is what I have so far:

for (int i = arr.length; i <= 0; --i) {
    if (arr[i] != 0) {
        arr[i] = arr.length - 1;
    }
}

Thanks!

Answer 1

Here is how i have implemented this. Time complexity: O(n) and Space Complexity: O(1) Below is the code snippet:

int arr[] = {0, 1, 0, 0, 2, 3, 0, 4, 0};
int i=0, k = 0;
int n = sizeof(arr)/sizeof(arr[0]);
for(i = 0; i<n; i++)
{
  if(arr[i]==0)
    continue;
  arr[k++]=arr[i];
}
for(i=k;i<n;i++)
{
  arr[i]=0;
}

output: {1, 2, 3, 4, 0, 0, 0, 0, 0}

Explanation: using another variable k to hold index location, non-zero elements are shifted to the front while maintaining the order. After traversing the array, non-zero elements are shifted to the front of array and another loop starting from k is used to override the remaining positions with zeros.

Answer 2

    int[] nums = { 3, 1, 2, 5, 4, 6, 3, 2, 1, 6, 7, 9, 3, 8, 0, 4, 2, 4, 6, 4 };
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 3) {
            list1.add(nums[i]);
        } else if (nums[i] != 3) {
            list2.add(nums[i]);
        }
    }
    List<Integer> finalList = new ArrayList<>(list2);
    finalList.addAll(list1);
}

}

Answer 3

int[] nums = {3,1,2,5,4,6,3,2,1,6,7,9,3,8,0,4,2,4,6,4};
    int i = 0;
    for(int j = 0, s = nums.length; j < s;) {
        if(nums[j] == 3)
            j++;
        else {
            int temp = nums[i];
            nums[i] = nums[j];``
            nums[j] = temp;
            i ++;
            j ++;
        }
    }

Answer 4

Two choices come to mind

1. Create a new array of the same size, then Iterate over your current array and only populate the new array with values. Then fill the remaining entries in the new array with "zeros"

2. Without creating a new array you can iterate over your current array backwards and when you encounter a "zero" swap it with the last element of your array. You'll need to keep a count of the number of "zero" elements swapped so that when you swap for a second time, you swap with the last-1 element, and so forth.

---

[Edit] following request for clarification

public class MyClass {

    public static void main(String[] args) {

        int[] elements = new int[] {1,2,3,4,0,5,6,0,7,8,9};

        int swapCount = 0;
        int lastIndex = elements.length-1;

        for(int i = lastIndex-1; i >=0; i--) {  // skip the very last element
            if(elements[i] == 0) {
                elements[i] = elements[lastIndex-swapCount];
                elements[lastIndex-swapCount] = 0;
                swapCount++;
            }
        }

        for(int i : elements) {
            System.out.print(i + ", ");
        }
    }
}

Gives you...

1, 2, 3, 4, 8, 5, 6, 9, 7, 0, 0, 

Answer 5

a = [ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 ]

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

print(a)
#op [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]

Answer 6

Time complexity = O(n), Space Complexity = O(1)

import java.util.Scanner;

public class ShiftZeroesToBack {

    int[] array;
    void shiftZeroes(int[] array) {

        int previousK = 0; 
        int firstTime = 0;

        for(int k = 0; k < array.length - 1; k++) {

            if(array[k] == 0 && array[k + 1] != 0 && firstTime != 0) {
                int temp = array[previousK];
                array[previousK] = array[k + 1];
                array[k + 1] = temp;
                previousK = previousK + 1;
                continue;
            }

            if(array[k] == 0 && array[k + 1] != 0) {
               int temp = array[k];
               array[k] = array[k + 1];
               array[k + 1] = temp;
               continue;
            }

            if(array[k] == 0 && array[k + 1] == 0) {
                if(firstTime == 0) {
                    previousK = k; 
                    firstTime = 1;
                }
            }

       }
   }

   int[] input(Scanner scanner, int size) {
       array = new int[size];
       for(int i = 0; i < size; i++) {
           array[i] = scanner.nextInt();
       }
       return array;
   }

   void print() {
       System.out.println();
       for(int i = 0; i < array.length; i++) {
           System.out.print(array[i] + " ");
       }
       System.out.println();
   }

   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       ShiftZeroesToBack sztb = new ShiftZeroesToBack();
       System.out.print("Enter Size of Array\t");
       int size = scanner.nextInt();
       int[] input = sztb.input(scanner, size);
       sztb.shiftZeroes(input);
       sztb.print();
   }

}