CareerCup

Complexity: O(n)

class PushZeroToLast
{
        public static void main (String[] args)
        {
                //int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
                int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9,0};
                int n = arr.length;
                pushZerosToLast(arr, n);
                System.out.println("Output: ");
                for (int i=0; i<n; i++)
                        System.out.print(arr[i]+" ");
        }

        static void pushZerosToLast(int arr[], int n)
        {
                int count = 0;

                for (int i = 0; i < n; i++)
                        if (arr[i] != 0)
                                arr[count++] = arr[i];

                while (count < n)
                        arr[count++] = 0;
        }
}

public static void moveZeroesToEnd(int[] arr) {
		int start = 0;
		int end = arr.length - 1;
		
		while (start < end) {
			while (arr[start] != 0 && start < arr.length - 1) 
				start++;
			while (arr[end] == 0 && end > 0) 
				end--;
			if (start >= end) break;

			// swap start with end
			int temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
		}
	}

public static int[] moveZeros(int[] array) {
    int j = array.length-1; 
    for (int i = array.length-1; i >= 0; i --){
      if (array[i] == 0) {
        array[i] = array[j];
        array[j] = 0; 
        j --; 
      }
    }
    return array; 
  }

void foo(int *a, int size)
{
	int i, j, mid, k;
	i = 0;j=size-1;mid=0;
	for (k=0;k<size;k++) {
		if (a[mid] > 0) {
		 	i++;
		 	mid++;
		} else {
			swap(a, mid, j);
			j--;
		}
	}
}

public static int[] moveZeros(int[] array) {
int j = array.length-1;
for (int i = array.length-1; i >= 0; i --){
if (array[i] == 0) {
array[i] = array[j];
array[j] = 0;
j --;
}
}
return array;
}

int[] move_zeroes(int[] arr)
{

ArrayList<Integer> ar=new ArrayList<>();


for(int i=0;i<arr.length;i++)
{
if(arr[i]==0)
ar.add(i);
}



int start_index=arr.length-ar.size();

int index=start_index;

//System.out.println(start_index);

for(int j=0;j<ar.size();j++)
{
 
    //System.out.println(ar.get(j));
    if(ar.get(j)<start_index)
    {
        while(arr[index]==0)
        {
            index++;
        }
        
        int tmp=arr[index];
        arr[index]=arr[ar.get(j)];
        arr[ar.get(j)]=tmp;
    }
        
}



return arr;

}

public void modify(int arr[])
{
	int i =0;
        int j =arr.length -1;

        while(i<arr.length)
        if(arr[i]==0)break;
 
       while(j>0)
        if(arr[j]!=0)break;

     while(i<j)
      {
         swap(i,j)
          while(i<arr.length)
        if(arr[i]==0)break;
 
       while(j>0)
        if(arr[j]!=0)break;
      }

   return
     
}

int st=0;
	for(int i=0;i<n;i++){
		if(a[i]!=0){
			a[st] = a[i];
			st++;
		}
	}
	while(st<n){
		a[st]=0;
		st++;
	}

public static void MoveZerosToTheEnd(int[] arr)
        {
            int start = 0;
            int end = arr.Length - 1;

            while (start < end)
            {
                if (arr[end] == 0)
                    end--;
                else if (arr[start] == 0)
                {
                    int tmp = arr[start];
                    arr[start] = arr[end];
                    arr[end] = tmp;
                    end--;
                    start++;
                }
                else
                    start++;
            }
        }

#include<iostream>

using namespace std;

int main()
{
    int a[10]={1,2,0,0,0,0,4,5,6,9},i,j,t;
	
	for(i=0,j=9;i<j;i++)
	{
	   if(a[i]==0)
	   { 
	     if(a[j]!=0)
	     {
	     	t=a[i];
	     	a[i]=a[j];
	     	a[j]=t;
	     	j--;
	     }
	     else
	     {
	     	--j;
	     		t=a[i];
	     	a[i]=a[j];
	     	a[j]=t;
	     }
	   	
	   }	
		
	}
	for(i=0;i<10;i++)
	{
		cout<<a[i];
	}

}

#include<iostream>

using namespace std;

int main()
{
int a[10]={1,2,0,0,0,0,4,5,6,9},i,j,t;

for(i=0,j=9;i<j;i++)
{
if(a[i]==0)
{
if(a[j]!=0)
{
t=a[i];
a[i]=a[j];
a[j]=t;
j--;
}
else
{
--j;
t=a[i];
a[i]=a[j];
a[j]=t;
}

}

}
for(i=0;i<10;i++)
{
cout<<a[i];
}


}

private static void moveZeroesToTheEnd(int[] arr){

        Stack zeroStack = new Stack();

        Stack nonZeroStack = new Stack();

        for(int i=0; i<arr.length; i++){
            if(arr[i]==0)
                zeroStack.push(0);
            else
                nonZeroStack.push(arr[i]);
        }


        int[] newArrayWithZeroesOnRight = new int[arr.length];

        for(int i=0; i<newArrayWithZeroesOnRight.length; i++){

            if(!nonZeroStack.isEmpty())
                newArrayWithZeroesOnRight[i] = (Integer)nonZeroStack.pop();
            else
                newArrayWithZeroesOnRight[i] = (Integer)zeroStack.pop();

        }

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

this can't be facebook question

void zeros2end(int a[], int size) {
    int next = size-1;
    int i = 0;

    while (i < next) {
        if (a[next] == 0) {
            next--;
            continue;
        }
        if (a[i] == 0) {
            swap(a[i], a[next]);
            next--;
            i++;
        }
        else i++;
    }

}

def zeros_on_right(numbers):
    last_unused = len(numbers) - 1
    curr_index = 0
    while curr_index < last_unused:
        if numbers[curr_index] == 0:
            numbers[curr_index], numbers[last_unused] = numbers[last_unused], numbers[curr_index]
            last_unused -= 1
        if numbers[curr_index] != 0:
            curr_index += 1
    return numbers

void mover(int* arr, int n)
{
	int end = n - 1;

	// Checking inputs	
	if ((NULL == arr) || (n <= 0))
		return;

	// Iterate the array
	while (i <= end)
	{
		// Check for zeros
		if (arr[i] == 0)
		{
			// Swap the elements at positions "i" and "end"
			arr[i] = arr[end];
			arr[end] = 0;

			// The next position for a zero decreases
			end--;
		}
		else
		{
			// Not a zero, move on
			i++;
		}
	}
}

public static void doIt(int[] arr) {
    if (arr == null) {
        return;
    }
    int low = 0;
    int high = arr.length -1;
    while (low < high) {
        if (arr[right] == 0) {
            --right;
            continue;
        }
        if (arr[left] != 0) {
            ++left;
            continue;
        }
        arr[left++] = arr[right];
        arr[right--] = 0;
    }
}

public static doIt(int[] arr) {
  if (arr == null) {
    return;
  }
  int left = 0;
  int right = arr. length - 1;
  while (left < right) {
    if (arr[right == 0) {
      --right;
      continue;
    }
    if (arr[left] != 0) {
      ++left;
      continue;
    }
    arr[left++] = arr[righht];
    arr[right] = 0;
  }
}

public static void doIt(int[] arr) {
		if (arr == null) {
			return;
		}

		int left = 0;
		int right = arr.length - 1;
		while (left < right) {
			if (arr[left] != 0) {
				++left;
				continue;
			}
			if (arr[right] == 0) {
				--right;
				continue;
			}
			arr[left++] = arr[right];
			arr[right--] = 0;
		}
	}

public static void doIt(int[] arr) {
		if (arr == null) {
			return;
		}

		int left = 0;
		int right = arr.length - 1;
		while (left < right) {
			if (arr[left] != 0) {
				++left;
				continue;
			}
			if (arr[right] == 0) {
				--right;
				continue;
			}
			arr[left++] = arr[right];
			arr[right--] = 0;
		}
	}

#include <iostream>
#include <vector>

using namespace std;

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

vector<int> moveZeros(vector<int> & inArr) {
    int start = 0;
    int end = (int) inArr.size() - 1;
    while(start < end) {
        while(inArr[start]!=0) {
            ++start;
        }
        while(inArr[end]==0) {
            --end;
        }
        if(start<end) {
            swap(inArr, start, end);
        }
    }
    return inArr;
}

simple python code
O(n2)

def move_0(l):
    for i in range(len(l)-1):
        for j in range(0, len(l)-1-i):
            if l[j] == 0:
                l[j+1] , l[j] = l[j], l[j+1]

mylist = [1, 2, 4, 0, 0, 12]
move_0(mylist)
print(mylist)

Python
O(n)

def move0(l):
    new = []
    for i in l:
        if i != 0:
            new.append(i)
    for i in l:
        if i == 0:
            new.append(i)
    return new

z = move0([1, 2, 4, 0, 0, 12])
print(z)

public void MoveZeros(int[] values)
{
	int start = 0;
	int end = values.Length - 1;

	while (start < end)
	{
		while (start < end && values[end] == 0)
			end--;
		while (start < end && values[start] != 0)
			start++;
		if (values[start] == 0)
		{
			values[start] = values[end];
			values[end] = 0;
		}
	}
}

public static void main(String[] args) {
		
		int[] num = {5,86,4,8,0,4,0,3,9,0,4,0,8,7,0,5,0};
		
		int leftCounter = 0;
		int rightCounter = num.length -1;
		do{
			if(0 == num[leftCounter]){
				
				while(rightCounter > leftCounter && num[rightCounter] == 0){
					rightCounter--;
				}
				
				num[leftCounter] = num[rightCounter];
				num[rightCounter] = 0; 		
			}
			
			leftCounter++;
		}while(leftCounter < rightCounter);
		
		for(int i : num){ System.out.print(i+" "); }
}

public static void main(String[] args) {
		
		int[] num = {5,86,4,8,0,4,0,3,9,0,4,0,8,7,0,5,0};
		
		int leftCounter = 0;
		int rightCounter = num.length -1;
		do{
			if(0 == num[leftCounter]){
				
				while(rightCounter > leftCounter && num[rightCounter] == 0){
					rightCounter--;
				}
				
				num[leftCounter] = num[rightCounter];
				num[rightCounter] = 0; 		
			}
			
			leftCounter++;
		}while(leftCounter < rightCounter);
		
		for(int i : num){ System.out.print(i+" "); }
}

Python 2.7.x code:

def movezeros(arr):
n = arr.count(0)
for i in xrange(n):
arr.remove(0)
arr.append(0)
return arr

C code O(n)

#include "stdio.h"
#include "stdlib.h"

#define LENGTH 10

void main()
{
int a[10]= {1,0,3,4,5,0,7,8,0,10};

int start=0;
int end =LENGTH-1;
int temp;


      while(start < end){
      // set the end to a non zero element
      while (a[end]==0) end--;

       if (a[start]==0)
       		{
                 // swap the 0 with the end element
		 temp=a[end];
		 a[end]=a[start];
		 a[start]=temp;
	        }
       start++;
      
      } // end while
      printf(" Array after processing is ");
      for(int i=0;i<LENGTH;i++)
      {
	      printf(" %d ",a[i]);
      }
}

O(N) implementation

// Shift all the zero's to the right of the array
void shift_zeros_right(int arr[], const int& sz)
{
	int i = 0, j = sz;
	while(i < j)
	{
		// Skip if the current element is a not zero
		if (arr[i] != 0)
		{
			++i;
			continue;
		}
		
		if (arr[j] != 0)
		{
			swap(arr, i, j);
			++i;
		}		
		--j;
	}
}

#include<stdio.h>
#define MAX 50
int main()
{
	int arr[MAX],n,i,j,temp,b[MAX];
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&arr[i]);
	i=0;
	j=0;
	while(i<n)
	{
		if(arr[i]!=0)
		{
			b[j]=arr[i];
			j++;
		}
		i++;
	}
	for(;j<n;j++)
	{
		b[j]=0;
	}
	for(i=0;i<n;i++)
	printf("%d\t",b[i]);
	return 0;
}

Time-complexity: O(n), Space-complexity: O(1)

public static void modify(int[] a) {
		int end = a.length - 1;
		for(int i=end;i >= 0;i--) {
			if(i == end && a[i] == 0) end--;
			else if(a[i] == 0) {
				a[i] = a[end];
				a[end] = 0;
				end--;
			}
		}
	}

Another Swift solution

func moveZerosToEnd(inputArray: [Int]) -> [Int] {
    var nonZerosArray: Array = [Int]()
    var zerosArray = [Int]()
    for number in inputArray {
        if number == 0 {
            zerosArray.append(number)
        }
        else {
            nonZerosArray.append(number)
        }
    }
    
    return nonZerosArray + zerosArray
}

O(n) Two phase solution- (1) first shift the elements by so many zeros found so far; (2) fill the number of zeros in the end

#include<vector>
#include<iostream>
using namespace std;

void pushZerosToEnd(vector<int> &v) {
  int count = 0;
  for(unsigned int i=0; i < v.size(); i++) {
    if (v[i] == 0) {
      count++;
    } else {
      v[i-count] = v[i];
    }
  }
  int i = v.size()-1;
  while(count--) {
    v[i] = 0;
    i--;
  }
}

int main() {
  
  int a[] = { 0, 1, 0, 2, 4, 0, 7, 0, 8};
  vector<int> v(a, a + sizeof(a)/sizeof(a[0]));
  
  pushZerosToEnd(v);
  for(auto itr = v.begin(); itr != v.end(); itr++) {
    cout<<*itr<<"\t";
  }
  
}

#include<vector>
#include<iostream>
using namespace std;

void pushZerosToEnd(vector<int> &v) {
  int count = 0;
  for(unsigned int i=0; i < v.size(); i++) {
    if (v[i] == 0) {
      count++;
    } else {
      v[i-count] = v[i];
    }
  }
  int i = v.size()-1;
  while(count--) {
    v[i] = 0;
    i--;
  }
}

int main() {
  
  int a[] = { 0, 1, 0, 2, 4, 0, 7, 0, 8};
  vector<int> v(a, a + sizeof(a)/sizeof(a[0]));
  
  pushZerosToEnd(v);
  for(auto itr = v.begin(); itr != v.end(); itr++) {
    cout<<*itr<<"\t";
  }
}

void moveallZeros(int arr[], int arraySize)
{
int frontPointer=0;
int backPointer=arraySize-1;
while (frontPointer < backPointer)
{
while(arr[frontPointer] != 0 && frontPointer < backPointer)
{
printf("%d incrementing fp\n", frontPointer);
frontPointer++;
}
while(arr[backPointer] ==0 && frontPointer < backPointer)
{
printf("%d incrementing fp\n", backPointer);
backPointer--;
}
if (frontPointer < backPointer)
{
swap(arr, frontPointer, backPointer);
frontPointer++;
backPointer--;
}
}
}

int[] zeroToRight(int[] numbers) {
        numbers.toList().sort { o1, o2 ->
            o1 == 0 ? 1 : (o2 == 0 ? -1 : 0)
        }
    }

PHP version:

<?php
$arr = [0, 4, 5, 7, 8, 0, 9, 0, 0, 4, 5];
rsort($arr);
print_r($arr);

P.S. I'm sure this is not facebook question.

Time Complexity : o(n) Space Complexity : o(n) ; requires additional array of the same size

Another solution could be write an sorting algo in descending order.

public static void modifyArray(int []input) {
		int []modifiedArray = new int[input.length];
		int startIndex = 0;
		int lastIndex = input.length -1;
		for(int i =0;i<input.length;i++) {
			if(input[i] == 0) {
				modifiedArray[lastIndex--] = input[i];
			} else {
				modifiedArray[startIndex++] = input[i];
			}
		}
		printArray(modifiedArray);
	}

You could define a comparison function and sort using std::sort().

bool myFunc(int a, int b)
{
  if(a == 0 || b == 0)
    return false;
  else
    return true;
}

Java:

private static int[] moveZerosToEnd(int[] arrayOfInteger){
        int temp;
        int end = arrayOfInteger.length -1;

        for(int i = 0; i < arrayOfInteger.length -1; i++){
            if(i < end){
                if(arrayOfInteger[i] == 0){
                    if(arrayOfInteger[end] == 0){
                        arrayOfInteger[end--] = arrayOfInteger[i];

                    }else{
                        temp = arrayOfInteger[end]; // 1
                        arrayOfInteger[end--] = arrayOfInteger[i];
                        arrayOfInteger[i] = temp;
                    }

                }
            }

        }

        return arrayOfInteger;
    }

def zeros2end(s):
    i = 0
    z = None # index of the first 0-element                                                        

    while i < len(s) - 1:
        if s[i] == 0:
            if z is None:
                z = i
	    if s[i+1] != 0: 
		s[z], s[i+1] = s[i+1], 0
                z += 1
	i += 1

def zeros2end(s):
    i = 0
    z = None # index of the first 0-element                                                        

    while i < len(s) - 1:
        if s[i] == 0:
            if z is None:
                z = i
	    if s[i+1] != 0: 
		s[z], s[i+1] = s[i+1], 0
                z += 1
	i += 1

We can do this in O(n) with O(1), constant, memory using the original array, by swapping elements.

We need two pointers, one starting at index zero (the right index), and one starting at n-1 (the right index).

We test each element at a[left_idx] to see if it's zero.

If it equal to zero, we swap it with the element at a[right_idx], or the element at the left size of the last zero we moved to the end. Since we put a zero at that index, we have to decrement right_idx.

If that element at the left_idx is not zero, we increment the right pointer.

We stop when the two pointers are at the same location.

def move_zeros_to_end(a):
    n = len(a)
    right_idx = n - 1
    left_idx = 0
        
    while left_idx < right_idx:
        if a[left_idx] == 0:
            a[left_idx], a[right_idx] = a[right_idx], a[left_idx]
            right_idx -= 1
        else:
            left_idx += 1
    
    return a

def movezeroes(self,s):
  begin=0
  end = len(s) - 1
  while begin< end:
     if s[begin] !=0:
        begin+=1
        continue
     if s[begin] == 0:
        while s[end] == 0:
             end-=1
        temp = s[end]
        s[end]=s[begin]
        s[begin] = temp
        begin+=1
        end-=1
  return s

One Liner:

def movezeroes(self,s):
   s.sort(key=lambda x:1 if x==0 else 0)
   return s

public class PutZerosAtEnd {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 5, 1, 5, 1, 0 ,3, 81, 32, 0, 12, 91, 0, 1, 0};
		zerosToEnd(arr);
		System.out.print("{ ");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("}");
	}
	
	public static void zerosToEnd(int[] arr) {
		//Sets position to swap to at the
		//end of the array.
		int swapPos = arr.length - 1;
		//continue moving backwards until it is not
		//equal to 0.
		while (swapPos > -1 && arr[swapPos] == 0) 
			swapPos--;
		
		//Go forward in the array until swapPos
		for (int i = 0; i < swapPos; i++) {
			//If an element is 0, swap it with
			//the element at swapPose.
			if (arr[i] == 0) {
				int temp = arr[swapPos];
				arr[swapPos] = arr[i];
				arr[i] = temp;
				// decrement swapPos until not pointing
				// to a 0.
				while (swapPos > -1 && arr[swapPos] == 0) 
					swapPos--;
			}
		}
		
	}
}

output:

{ 1 3 5 1 5 1 1 3 81 32 91 12 0 0 0 0 }