An array A is given, A contains only 0s and 1s in random order. The task is to Segregate 0s on left side and 1s on right side of the array (sort the array) in O(n) time complexity.

##### Example 1: Segregate 0s and 1s in: {1, 0, 1, 0}

**Input:** {1, 0, 1, 0}

**Output:** {0,0,1,1}

##### Example 2: Segregate 0s and 1s in: {0, 1, 0, 1, 0, 0, 1, 1, 1, 0}

**Input:** {0, 1, 0, 1, 0, 0, 1, 1, 1, 0}

**Output:** {0,0,0,0,0,1,1,1,1,1}

## Solutions

### Method 1: Dutch National Flag

In this approach we will use famous Dutch National Flag algorithm. The idea is to divide the array in two parts such that; [1 to low-1] will have 0s, [low to high-1] will have unsorted elements and [high to n] will have 1s.

Start with low=0, high=n-2 and traverse the array until low

package com.cb.arrays; import java.util.Arrays; import java.util.stream.Collectors; /* * O(n) * Dutch National Flag * */ public class A2_SortArrayContaining01s { private static void sort(int[] arr, int n) { if (arr == null || n < 1) return; int low = 0, high = n - 1; while (low < high) { if (arr[low] == 0) low++; else if (arr[low] == 1) { int tmp = arr[low]; arr[low] = arr[high]; arr[high] = tmp; high--; } } } // Just to print output array private static void printArray(int[] arr) { System.out.println(Arrays.stream(arr).mapToObj(Integer::toString).collect(Collectors.joining(","))); } public static void main(String[] args) { int[] arr = {1, 0, 1, 0}; sort(arr, arr.length); printArray(arr); int[] arr1 = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0}; sort(arr1, arr1.length); printArray(arr1); } }

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

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.

### Method 2: Using two indexes to traverse

We can solve this problem in O(n) time using two variables, i=0, j=n-1; The idea is to traverse the array until i

package com.cb.arrays; import java.util.Arrays; import java.util.stream.Collectors; /* * O(n), Simple Approach * */ public class A2_1_SortArrayContaining01s { private static void sort(int[] arr, int n) { if (arr == null || n < 1) return; int i = 0, j = n - 1; while (i < j) { if (arr[i] == 1) { while (arr[j] == 1 && j > i) j--; int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } i++; } } // Just to print output array private static void printArray(int[] arr) { System.out.println(Arrays.stream(arr).mapToObj(Integer::toString).collect(Collectors.joining(","))); } public static void main(String[] args) { int[] arr = {1, 0, 1, 0}; sort(arr, arr.length); printArray(arr); int[] arr1 = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0}; sort(arr1, arr1.length); printArray(arr1); } }

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

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.