MoveZeros.java

/**
 * Given an integer array. Move all zero elements to the end without changing the order of other numbers.
 * 
 * Space Complexity: O(1)
 * Time Complexit: O(n) is ideal. But O(n^2) is okay.
 */

public class MoveZeros {
    
    // [1,2,0,4,3,0,5,0]
    int[] moveZeros(int[] arr){
        // count all zeros
        int numZeros = 0;
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == 0)
                numZeros++;
        }


        // [1,2,0,4,3,0,5,0]
        // [1,2,4,0,3,0,5,0]
        // [1,2,4,3,0,0,5,0]
        // [1,2,4,3,5,0,0,0]

        for(int i = 0; i < arr.length - numZeros; i++){
            if(arr[i] == 0){
                // find next non zero element
                for(int j = i+1; j < arr.length; j++){
                    if(arr[j] != 0){
                        arr[i] = arr[j];
                        arr[j] = 0;
                        break;
                    }
                }
            }
        }
        
        return arr;
    }

    public static void main(String[] args) {
        MoveZeros solution = new MoveZeros();
        int[] sample = new int[]{1,2,0,4,3,0,5,0};
        int[] answer = solution.moveZeros(sample);

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