Monday, March 9, 2015

Move all zero to left or right in an array

Move zero to right:
Move zero integers to end of array.
Given an array of integers. Move all non-zero elements to the left of all zero elements.
Solution:
Run time complexity O(n), constant space.
public static void moveZeroToEnd(int[] n) {
  int count = 0;
  
  for(int i = 0; i < n.length; i++) {
   if(n[i] != 0) {
    n[count] = n[i];
    count++;
   }
  }
  
  while(count < n.length) {
   n[count] = 0;
   count++;
  }
 }
Follow up: move zero to right in minimum swap.
You are given an integer array which contains some zeros. Move the zeros to the right side of the array with minimum number of swaps. The order of the original array can be destroyed.
We can do this in at most n/2 swaps.
public static void moveZeroToEndMinSwap(int[] n) {
  int l = 0;
  int r = n.length - 1;
  while(l < r) {
   if(n[l] == 0 && n[r] != 0) {
    int temp = n[r];
    n[r] = n[l];
    n[l] = temp;
    l++;
    r--;
   }else {
    if(n[l] != 0) {
     l++;
    }
    if(n[r] == 0) {
     r--;
    }
   }
  }
 }

Move zero to left:
Move zero integers to begin of array.
Given an array of integers. Move all non-zero elements to the right of all zero elements.
Solution
Run time complexity O(n), constant space.
public static void moveZeroToRight(int[] n) {
  int count = n.length - 1;
  for(int i = n.length - 1; i >= 0; i--) {
   if(n[i] != 0) {
    n[count] = n[i];
    count--;
   }
  }
  
  while(count >= 0) {
   n[count] = 0;
   count--;
  }
 }
Follow up: move zero to left in minimum swap.
You are given an integer array which contains some zeros. Move the zeros to the left side of the array with minimum number of swaps. The order of the original array can be destroyed.
We can do this in at most n/2 swaps.
public static void moveZeroToBeginMinSwap(int[] n) {
  int l = 0;
  int r = n.length - 1;
  while(l < r) {
   if(n[r] == 0 && n[l] != 0) {
    int temp = n[l];
    n[l] = n[r];
    n[r] = temp;
    l++;
    r--;
   }else {
    if(n[l] == 0) {
     l++;
    }
    if(n[r] != 0) {
     r--;
    }
   }
  }
 }

No comments:

Post a Comment