CareerCup

public static void moveNonZeroToLeft(int[] array)
  {
    int w = 0;
    for (int r = 0; r < array.length; r++)
    {
      if (array[r] != 0)
      {
        array[w++] = array[r];
      }
    }
    for (; w < array.length; w++)
    {
      array[w] = 0;
    }
  }

another linear time algorithm based on `partition` in quick sort:

void sortZero(vector<int> &vec) {
    vector<int>::iterator left = vec.begin(), right = vec.end();
    while (left != right) {                                                                                                                                                     
        if (*left) {
            left++;
        }   
        else {
            int tmp = *(right - 1); 
            *(right - 1) = *left;
            *left = tmp;
            right--;
        }   
    }   
}

int[] array =  new int[10] {1,2,4,6,0,7,0,2,1,9};
int[] newarray = new int[10];
int j = 0;
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] != 0)  newarray[j++] = array[i]; 
               
            }

def move(lst):
    return [x for x in lst if not x == 0] + [0] * lst.count(0)

print(move([1, 0, 6, 0, -4, 2, 5, 1]))  # [1, 6, -4, 2, 5, 1, 0, 0]
print(move([1, 2, 3, 4, 5, 6, 7, 8]))   # [1, 2, 3, 4, 5, 6, 7, 8]

def move(lst):
    tmp = list()
    zeros = 0
    for x in lst:
        if x == 0:
            zeros += 1
        else:
            tmp.append(x)
    return tmp + [0] * zeros
    # return [x for x in lst if not x == 0] + [0] * lst.count(0)

print(move([1, 0, 6, 0, -4, 2, 5, 1]))  # [1, 6, -4, 2, 5, 1, 0, 0]
print(move([1, 2, 3, 4, 5, 6, 7, 8]))   # [1, 2, 3, 4, 5, 6, 7, 8]

This way only have to pass through the 'lst' once.

public int[] Move(int[] input)
        {
            if (input.Length == 0)
                return input;

            int shift = 0;
            for (int i = 0; i < input.Length; i++)
            {
                if (shift > 0 && input[i] != 0)
                    input[i - shift] = input[i];
                if (input[i] == 0)
                    shift = shift + 1;
            }
            if (shift == 0)
                return input;

            for (int i = input.Length - shift; i < input.Length; i++)
            {
                input[i] = 0;
            }
            return input;
        }

public void move(int[] array) {
		int  i = 0 , R = array.length - 1;
		for (; i < R ; ++i) {
			 while (R >=0 && array[R] == 0) R--;
			 if ( i < R && array[i] == 0) {				 
				 array[i] = array[R] ;
				 array[R] = 0;				 
			 }
		}
	}

void zerosToLeft(vector<int> &V) {
	int wall = 0;
	for(int i = 0; i < V.size(); i++) 
		if(V[i] == 0) swap(V[wall++], V[i]);
}

#include<stdio.h>
void main()
{
        int arr[10] = {1,2,0,0,5,0,4,3,0,1};
        int i,j,zero;
        for(i=0;i<10;i++)
        {
                if(arr[i] != 0)
                {
                        continue;
                }
                zero = i;
                for(j =i+1;j<10;j++)
                {
                        if(arr[j] != 0)
                        {
                                arr[zero] = arr[j];
                                arr[j] = 0;
                                break;
                        }
                }
        }
        for(i =0;i<10;i++)
        {
                printf("%d",arr[i]);
        }
}

Pretty easy. Here's another linear time, constant memory solution in Scala:

object MoveLeft {
	def main(args: Array[String]) = {
	    var a = args(0).split(",").map(_.toInt).toArray
	    var firstZeroPos = -1
	    for(i <- 0 until a.length) {
            if(a(i) == 0 && firstZeroPos == -1) {
            	firstZeroPos = i
            } else
            if(a(i) != 0 && firstZeroPos != -1) {
            	a(firstZeroPos) = a(i)
            	a(i) = 0
            	firstZeroPos += 1
            }
	    }

	    println(a.mkString(","))
	}
}

void zerosAtEnd(int arr[SIZE])
{
	int len = SIZE;
	int cnt =0;
	int temp;
	for(int i=0;i<len-cnt;i++)
	{
		if(arr[i] == 0)
		{
			//count the zeroes
			cnt++;
			//if number of zeros and non-zeros equal to len 
			if((i+cnt)==len)
				break;
			else
			{
				//swap the zero and non zero elements starting from end of array
				temp = arr[i];
				//while swapping if any element from the end is found zero
				//then swap with previous element
				if(arr[len-cnt]==0)
					cnt++;
				arr[i] = arr[len-cnt];
				arr[len-cnt] = temp;
			}
		}
	}
	for(int i=0;i<len;i++)
	{
		cout << ' ' << arr[i];
	}

}

import java.util.Arrays;

public class FacebookInterview {
	
	// main
	public static void main(String[] args) {
		int[] input = {0, 1, 3, 4, 0, 3, 0, 5, 1, 7};
		System.out.println(Arrays.toString(moveAllZeroesToFront(input)));
	}

	// swaps elements at index a with index b
	public static void swap(int[] input, int a, int b) {
		int temp = input[a];
		input[a] = input[b];
		input[b] = temp;
	}

	// moves all zero elements to front in constant space
	public static int[] moveAllZeroesToFront(int[] input) {
		
		int front = 0;
		int tail  = input.length - 1;
		while (front <= tail) {
			while (input[front] == 0) {
				front++;
			}
			while (input[tail] != 0) {
				tail--;
			}
			if (front < tail) swap(input, front, tail);
		}
		return input;
	}

}

I've made one that's quite tight and also stable:

#include <iostream>

//Solution
void MoveNonZerosToTheLeft(int array[], int size)
{
    int insertPoint = 0;
    for (int i = 0; i < size; ++i)
    {
        if (array[i] == 0) continue;
        array[insertPoint] = array[i];
        if ( i > insertPoint++ ) array[i] = 0;
    }
}

// Test Code
int main(int argc, const char * argv[])
{
    int testArray[] = { 0,0,0,1,2,3,4,5,0,6,7,8,9,0,10,0 };
    MoveNonZerosToTheLeft(testArray, 16);
    for (int i = 0; i < 16; ++i) std::cout << testArray[i] << " ";
    std::cout << std::endl;
    return 0;
}

var array = [0,2,0,5,3,4,3,2,0,4,3,2,4,2];
var temp = [];
var count = 0;

for(number in array){
    
    if(array[number] !== 0){
        temp.push(array[number]);
        
    }else{
        count++;
    }
    
}

// insert
for(var i = 0; i<count; i++){
    temp.push(0);
}

console.log(temp)

A linear time, constant space solution in Java.

package fb;

import java.util.Arrays;

public class IntegerSorting {

	
	public static int[] nonZeroToLeft(int[] array) {
		
		int i,j;
		i=0;
		j=array.length-1;
		
		while(i<j) {
			while(array[i]!=0) i++;
			while(array[j]==0) j--;
			swap(i,j,array);
			i++;
			j--;
		}
		return array;
	}
	
	public static void swap(int i, int j, int[] array) {
		
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	public static void main(String[] args) {
		int[] array = {0,3,-5,0,0,2,999,0};
		
		System.out.println(Arrays.toString(nonZeroToLeft(array)));
	}
}

# Given an array of integers. 
# Move all non-zero elements to the left of all zero elements.

def move_array(array):
    ''' assume
    contains negative number
    e.g. 1,0,6,0,-4,2,5,1
    out: 1,6,-4,2,5,1,0,0
    '''
    
    l = len(array)
    i = 0
    while i < l:
        # try to move i-th element to the right
        if array[i] == 0:
            # shift i-th element to the right until the end, or 0 is reached
            shift_array(array, i)
        print_line(array)
        i+=1
        
    print_line(array)
        
def shift_array(array, i):
    l = len(array)
    j = i + 1
    while j < l:
        tmp = array[j]
        array[j] = array[j-1]
        array[j-1] = tmp
        j += 1
        
            
def print_line(array):
    line = ""
    for a in array:
        line += str(a) + " "
    print line
    
if __name__ == '__main__':
    move_array([1,0,6,0,-4,2,5,1])

/*
*
* On my first thought, I will loop through array one-by-one. If find 0, move to the end of element. Otherwise, do nothing.
*
* If you ask about time complexity and space.
*
* It would take O(n^2) in the worst case because we would have to move all elements to its front by 1.
* Space would be O(1)
*
* PseudoCode
* Func MoveZeros(array A)
* 1. loop i in array A
* 1.1 if i == 0 then tmp = i
* 1.2 Move all element after i up by 1 element
* 1.3 Put i in the last element of array A
*
* We can do better by giving index pointer of "k" at the end of array to recognise all zero elements we put at the end of array.
* So, we will loop through element of array from beginning but if we find 0, we will swap that element with index "k"
*
* PseudoCode
* Func MoveZeros(array A)
* 1. set k = A.size() - 1
* 2. loop i = 0 -> A.size()-1 and i < k
* if a[i] == 0; then
* - swap a[i] with a[k]
* - k--
* - i++
* else
* - i++
*
* How about time complexity and space for this?
*
* Time complexity : O(n)
* Space complexity : O(1)
*
*/

The final code is below where we can add number to stdin.

#include<iostream>
#include<vector>

using namespace std;

void swap(int &a,int &b){ int tmp = a;a=b;b=tmp;}

int main(void){
  vector<int> list;
  while(true){
    int i; cin>>i;
    if(cin.eof()){
      break;
    }
    list.push_back(i);
  }
  copy(list.begin(),list.end(),ostream_iterator<int>(cout," ")); cout<<endl;
  int k = list.size()-1;
  for(int i = 0 ;i<list.size() && i<k;){
    if(list[i]==0){
      swap(list[i],list[k]);
      k--;
    }else{
      i++;
    }
  }
  copy(list.begin(),list.end(),ostream_iterator<int>(cout," ")); cout<<endl;
  return 0;
}

1)keep original order
public int move(int[] arr) {
int read=0;
int write=0;
while(read<=arr.length-1) {
if(arr[read]!=0 && read!=write) {
arr[write++]=arr[read];
}
read++;
}
return write;

}

2) no need to keep order
public void move(int[] arr) {
if(arr==null || arr.length==0) return;
int lo=0;
int hi=arr.length-1;
while(lo<hi) {
if(arr[lo]!=0) lo++;
else if(arr[hi]==0) hi--;
else { arr[lo]=arr[hi]; lo++; hi--; }
}
return lo;

}

Feedback is welcomed:

int[] a = {0, 2, 0, 9, 0, 0, 8};

        for (int i = 0; i < a.length - 1; i++) {

            int j = i + 1;

            while (j > 0 && a[j - 1] == 0) {
                j--;
            }

            if (a[j] == 0) {
                int temp = a[j];
                a[j] = a[i + 1];
                a[i + 1] = temp;
            }
        }

        Utils.printArray(a);

In C#...

List<Int32> Values;
IEnumerable<Int32> SortedValues;

//init values to your initial values
//Values = new List<int>() { 0, -1, 3, 23, 50, -1, -9, 100 };

SortedValues = Values.OrderBy(v => v == 0);

public static void move0s(int[] arr){
	if(arr == null){
		throw new NullPointerException();
	}
	int front = 0;
	int end;
	//find index of the first non-0 at the end
	for(end = arr.length -1; end > -1 && arr[end] == 0; end--);
	//while there are unprocessed values
	while(front < end){
		//if the first value is a 0
		if(arr[front] == 0){
			//swap the value
			arr[front] = arr[end];
			arr[end] = 0;
			//find the next non-0 from the left
			for(; end > start && arr[end] == 0; end--);
		}
		front++;
	}
}

One pass with swift:

func zerosToTheLeft(inout input:Array<Int>) {
	var position = 0;
	input.count.times { i in
		if input[i] == 0 {
			swap(&input[i], &input[position++])
		}
	}
}

var input = [1, 2, 5, 3, 5, 0, 2, 6, 8, 0]
zerosToTheLeft(&input)

One with Objective C:

+ (NSArray *)moveTheZeros:(NSArray *)nums {
  NSInteger x = 0;
  NSMutableArray *ourNums = [nums mutableCopy];

  for (NSNumber *num in nums) {
    if (num.integerValue == 0) {
      [ourNums removeObjectAtIndex:x];
      [ourNums insertObject:@(0) atIndex:0];
    }
    x++;
  }
  return ourNums;

Go from left;
Find 0 in the index i;
Go from right
Replace first non 0 on the index l with the 0 from i.

In place... O(n)

int[] a = { .........};
int l = a.length -1;
for(int i=0; i<=l; i++){

    if(a[i] != 0)
        continue;

    for(int j = l; l>i; l--){
        if(a[l] != 0){
            swap(i, l);
            break;
        }
 }

Go from left;
Find 0 in the index i;
Go from right
Replace first non 0 on the index l with the 0 from i.

In place... O(n)

int[] a = { .........};
int l = a.length -1;
for(int i=0; i<=l; i++){

    if(a[i] != 0)
        continue;

    for(int j = l; l>i; l--){
        if(a[l] != 0){
            swap(i, l);
            break;
        }
 }

#include<iostream>
using namespace std;
int respos=0;
void fillNonZero2Right(int array[],int pos,int size,int result[])
{
        if(pos<size)
        {
                if(array[pos]==0)
                {
                        result[respos++] = array[pos];
                        fillNonZero2Right(array,pos+1,size,result);
                }
                else
                {
                        fillNonZero2Right(array,pos+1,size,result);
                        result[respos++] = array[pos];
                }
        }
}
int main()
{
        int a[] = {0,1,0,2,0,3,0,0,0,11,22,0,4,0,0,0,1,2,0,0,1,2},result[25];
        fillNonZero2Right(a,0,22,result);
        for(int i=0;i<22;i++)
        {
                cout<<result[i]<<endl;
        }
}
~

public static int [] move_the_zeros_to_right(int[] array) {
Arrays.sort(array);
int tempArray[] = new int[array.length];
int j = 0;
for (int i = array.length - 1; i >= 0; i--) {
tempArray[j++] = array[i];
}
return tempArray;
}

Similar solution, slightly different implementation

def move(array):
    start = 0;
    end = len(array)-1;
    while (end != start):
        while (array[end] ==0) and (end != start):
            end -= 1
        while (array[start] != 0) and (end != start):
            start += 1
        
        array[start],array[end] = array[end],array[start]
    return array
    


print(move([1, 0, 6, 0, -4, 2, 5, 1]))  # [1, 6, -4, 2, 5, 1, 0, 0]
print(move([1, 2, 3, 4, 5, 6, 7, 8]))   # [1, 2, 3, 4, 5, 6, 7, 8]

Similar solution, slightly different implementation.
Space = O(1)
Time = O(n)

def move(array):
    start = 0;
    end = len(array)-1;
    while (end != start):
        while (array[end] ==0) and (end != start):
            end -= 1
        while (array[start] != 0) and (end != start):
            start += 1
        
        array[start],array[end] = array[end],array[start]
    return array
    


print(move([1, 0, 6, 0, -4, 2, 5, 1]))  # [1, 6, -4, 2, 5, 1, 0, 0]
print(move([1, 2, 3, 4, 5, 6, 7, 8]))   # [1, 2, 3, 4, 5, 6, 7, 8]

#include<iostream>
using namespace std;

void swap(vector<int> & v, int i, int j) {
    int temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

int main() {

    int N = 5;
    
    vector<int> v(N);
    v[0] = 1;   v[1] = 0;  v[2] = 0;   v[3] = 2;  v[4] = 2; 
    for(int i=0;i < N; i++) cin>>v[i];

    int last = N-1;
    for(int i=0; i < N; i++) {
        if(v[i] == 0 && i < last) {
            swap(v, i, last);
            last--;
        }
    }

    for(int i = 0; i < N; i++) cout<<v[i]<<"\t";
    cout<<endl;
}

for all the c++ lovers out there

void non_zero(std::vector<int>& v){
	std::partition(v.begin(), v.end(), [](int x){ return x != 0; });
}

public static void main(String args[]) {
        int[] input = { 0, 1, 2, 3, 4, 0, 34, 0, 3, 2 };
        int end = input.length-1;
        int start = 0;
        while (start <= end) {
            while (input[start] != 0) {
                start++;
            }
            while (input[end] == 0) {
                end--;
            }
            if (start <= end) {
                int temp = input[start];
                input[start] = input[end];
                input[end] = temp;
                start++;
                end--;

            }
        }
    }

My solution with C++, which inspired by partition function in quick-sort:

void shuffle_zero(int A[], int n){
	if(n == 0) return;
	int index = 0;//index indicates the position where non-zero element should place
	
	for(int i = 0; i < n; i++){
		if(A[i] != 0){
			swap(A[index++], A[i]);
		}
	}
}

Almost all solution listed above is having O(n^2) complexity.

I tried solving it in O(n) .

public static void arrangeAllElements(int[] arr){
			if(arr.length<=1) return ;
			int low = 0;
			int high = arr.length-1;
			while(low<=high){
				if((arr[low]!=0&&arr[high]==0)){
					low++;
					high--;
				}
				else if(arr[low]!=0&&arr[high]!=0){
					low++;
				}
				else if(arr[low]==0 && arr[high]!=0){
					swap(arr,low,high);
					low++;high--;
				}
				else if(arr[low]==0&&arr[high]==0){
					high--;
				}
			}
		}
		private static void swap(int[] arr, int low, int high) {
			int temp = arr[low];
			arr[low] = arr[high];
			arr[high] = temp;
			
		}
		public static void main(String[] args) {
			int[] arr = {9, 8, 0, 1, 2, 0, 7};
			arrangeAllElements(arr);
			for(int i:arr){
				System.out.println(i+" ");
			}
			
			System.out.println("\nsecond array");
			int[] arr1 = {0, -9, 0, 0, 0, 0, 0};
			arrangeAllElements(arr1);
			for(int i:arr1){
				System.out.println(i+" ");
			}
		}

OO JS implementation

time complexity of O(n)
Space complexity O(n)

var a = [1, 0, 2, 0, 4, 0, 5, 0, 9, 10, 11];


function propRight() {
    this.count = 0;
    this.result = [];
}
propRight.prototype = {
    constructor: propRight,
    go: function(arr) {
        for (i = 0; i < arr.length; i++) {
            if (arr[i] === 0) {
                this.count++;
            } else {
                this.result.push(arr[i]);
            }
        }
        for (i = 0; i < this.count; i++) {
            this.result.push(0);
        }
        return this.result;
    }

}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void partition(int *a, int n) {
    int index = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != 0) {
            swap(&a[i], &a[index++]);
        }
    }
}

int main() {
    int a[10] = {3, 0, 5, 2, 6, 0, 1, 0, 0, 3};
    partition(a, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

public static void main(String[] args) {
	int[] array = new int[] {1,2,3,0,7,0,10, 0, 11, 13, 0, 15, 0, 0, 0, 4, 5, 6, 7, 8};
	separateZerosFromNonZeros(array);
}

public static void separateZerosFromNonZeros(int[] array) {
	int right = array.length -1;
	int left = 0;
	for(int i = 0; i <= right; ++i) {
		if(array[left] == 0) {
			if(array[right] != 0) {
				array[left] = array[right];
				array[right] = 0;
				++left;
			}
			--right;
		}
		else {
			if(array[right] != 0) {
				++left;
			} else{
				--right;
			}
	        }
	}
	System.out.println("After: ");
	for(int i = 0; i < array.length; ++i) {
		System.out.print(array[i] + ", ");
	}
}
//Output: 1, 2, 3, 8, 7, 7, 10, 6, 11, 13, 5, 15, 4, 0, 0, 0, 0, 0, 0, 0,

void moveNonZeroToLeft(int array[], int size){
int pos = 0;
for(int i = 0; i < size; i++){
if(array[i] > 0){
array[pos++] = array[i];
}
}
for(; pos < size; pos++){
array[pos] = 0;
}
}

void zerosToRight(int * arr, int size)
{
	int ind = size - 1;
	for (int a = 0; a < size - (size - 1 - ind);a++)
	{
		if (arr[a] == 0)
		{
			arr[a--] = arr[ind--];
			arr[ind+1] = 0;
		}
	}
}

Here is my code in Java to solve this problem -:

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;

public class MoveAllNonZeroElementsToLeftOfAllZeroElements {
	public static void main(String[] args) throws IOException{
		int start = 0;
		int end = integerArray.length - 1;
		while(start <= end){
			if(integerArray[start] == 0 && integerArray[end] != 0){
				int temp = integerArray[start];
				integerArray[start] = integerArray[end];
				integerArray[end] = temp;
				++start; --end;
			}else if(integerArray[start] != 0 && integerArray[end] != 0){
				++start;
			}else if(integerArray[start] == 0 && integerArray[end] == 0){
				--end;
			} else{
				++start;
			}
		}
		
		for(int i = 0; i < integerArray.length; ++i)
			System.out.print(integerArray[i] + " ");
	}
}

Simple clean solution

public static void MoveZeroToRight(int[] A)
{
	if(A == null)
		return;

	int head = 0;
	int tail = A.Length - 1;

	while(head > tail)
	{
		bool head0 = A[head] == 0;
		bool tail0 = A[tail] == 0;

		if(head0 && !tail0)
		{
			A[head] = A[tail];
			A[tail] = 0;

			head++;
			tail--;
		}
		else if(!head0)
		{
			head++;
		}
		else if(tail0)
		{
			tail--;
		}
	}
}

Here is the C++ solution. Running time is O(N)

#include <iostream>
using namespace std;
void swap(int * list, int s, int d)
{
	int tmp = list[s];
	list[s] = list[d];
	list[d] = tmp;
}

void partition(int *list, int len)
{
	int zero = len-1;
	int i = 0;
	while(i <zero)
	{
		if (list[zero] == 0)
		{
			zero--;
		} else if (list[i] != 0)
		{
			i++;
		}
		else if (i < zero)
		{	
			swap(list, i, zero--);
		}
	}
}

int main()
{
	int  input[8] = {1,0,6,0,3,0,0,1};
	partition(input, 8);
	for (int i = 0; i < 8; i++)
		cout<<input[i]<<",";
	cout<<endl;
}

import java.util.Arrays;


public class Shift {
        public Shift(){
        }
        public int[] shiftNums(int[] original){
                //variables
                int start = 0;
                //loop
                for (int i = original.length-1;i>=0;i--){
                        if (original[i] == 0){
                                while (original[start] == 0){
                                        start++;
                                }
                                original[i] = original[start];
                                original[start] = 0;
                                start++;

                        }
                        if (start == i){
                                return original;
                        }
                }
        return original;
        }

        public static void main(String[] Args){
                Shift test = new Shift();
                int[] a = {1,0,5,0,7,9,0,3};
                test.shiftNums(a);
                System.out.println(Arrays.toString(a));
        }

}

import java.util.Arrays;


public class Shift {
        public Shift(){
        }
        public int[] shiftNums(int[] original){
                //variables
                int start = 0;
                //loop
                for (int i = original.length-1;i>=0;i--){
                        if (original[i] == 0){
                                while (original[start] == 0){
                                        start++;
                                }
                                original[i] = original[start];
                                original[start] = 0;
                                start++;

                        }
                        if (start == i){
                                return original;
                        }
                }
        return original;
        }

        public static void main(String[] Args){
                Shift test = new Shift();
                int[] a = {1,0,5,0,7,9,0,3};
                test.shiftNums(a);
                System.out.println(Arrays.toString(a));
        }

}