Showing posts with label Segregate 0s and 1s in an array by looping only once. Show all posts
Showing posts with label Segregate 0s and 1s in an array by looping only once. Show all posts

Segregate 0s and 1s in an array by looping only once

In this tutorial we see how to segregate 0s and 1s in an array just by looping only once, ie. O(n).
With simple logic we will me maintaining 2 pointers like i and j where i will be pointing 0th location and j will be pointing Nth location.
Just we need to loop array and check if each index value and need to segregate accordingly. Lets see simple Java example to Segregate 0s and 1s in an array and an important by looping array only once.
SegregateArray



public class SegregateArray {

 public static void main(String[] args) {

  int[] arr = new int[] { 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1 };

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

    if (arr[j] == 0) {
     arr[i] = 0;
     arr[j] = 1;
    }
    j--;
   } else {
    i++;
   }
  }

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


OUTPUT:



0, 
0, 
0, 
0, 
0, 
0, 
0, 
1, 
1, 
1, 
1, 
1, 
1,