Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

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

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

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

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