Sort Array of 0s and 1s.
You are given an array ‘A’ of size ‘N’ containing only 0s and 1s. You have to sort the array by traversing the array only once.

For Example:

For the following array: [0 1 1 1 0 0 1] The output should be [0 0 0 1 1 1 1].

Note:

You have to sort the array in place.

Input Format:

The first line will contain a single integer ‘T’ denoting the number of test cases. Then the test cases follow. The first line of each test case will contain a single integer ‘N’, denoting the size of the array. The second line of each test case will contain ‘N’ space-separated integers, denoting the elements of the array.

Output Format:

For each test case, print the input array after sorting it.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Sort Array of 0s and 1s.

You are given an array ‘A’ of size ‘N’ containing only 0s and 1s. You have to sort the array by traversing the array only once.

For Example:

For the following array:
[0 1 1 1 0 0 1]

The output should be [0 0 0 1 1 1 1].

Note:

You have to sort the array in place.

Input Format:

The first line will contain a single integer ‘T’ denoting the number of test cases. Then the test cases follow.

The first line of each test case will contain a single integer ‘N’, denoting the size of the array.

The second line of each test case will contain ‘N’ space-separated integers, denoting the elements of the array.

Output Format:

For each test case, print the input array after sorting it.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
A[i] = 0 or 1

Time Limit: 1 sec.

Accepted Answer

Technical knowledge

Accepted Answer

Count 0s and 1s.

Count the number of 0s and 1s present in the input array. Suppose “count0” and “count1” be the number of 0s and 1s present respectively. Then replace the first “count0” elements in the array with 0 and the remaining elements with 1.

Algorithm:

Declare an integer variable “count0” and initialize it with 0.
Iterate over the array.
- If the current element is 0.
  - Increment the “count0” variable.
Iterate over the array from 0 to (“count0” - 1) and mark all the elements as 0.
Iterate over the array from “count0” to (‘N’ - 1) and mark all the elements as 1.

Space Complexity: O(1)Explanation:

O(1).

Constant space is used.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

Since we are iterating over the array, the time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    where N is the size of the array.

*/

public class Solution {

  

    public static void sort0and1(int n, int[] A) {

    

        // Declare an integer variable count and initialize it with 0.

        int count0 = 0;

    

        // Iterate over the array.

        for(int i = 0; i < n; i++){

    

            // If the current element is 0.

            if(A[i] == 0){

    

                // Increment the count variable.

                count0++;

            }

        }

    

        // Iterate over the array from 0 to (count - 1) 

        // and mark all the elements as 0.

        for(int i = 0; i < count0; i++){

            A[i] = 0;

        }

    

        // Iterate over the array from count to (N - 1) 

        // and mark all the elements as 1.

        for(int i = count0; i < n; i++){

            A[i] = 1;

        }

    

    }

}

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(1)

    where ‘N’ is the size of the array.
'''

def sort0and1(n, A):
    
    # Declare an integer variable “count0” and initialize it with 0.
    count0 = 0

    # Iterate over the array.
    for i in range(n):

        # If the current element is 0.
        if(A[i] == 0):

            # Increment the “count0” variable.
            count0 += 1
        
    

    # Iterate over the array from 0 to (“count0” - 1) 
    # and mark all the elements as 0.
    for i in range(count0):
        A[i] = 0
    

    # Iterate over the array from “count0” to (‘N’ - 1) 
    # and mark all the elements as 1.
    for i in range(count0, n):
        A[i] = 1

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where ‘N’ is the size of the array.
*/

void sort0and1(int n, vector &A){
    
    // Declare an integer variable “count0” and initialize it with 0.
    int count0 = 0;

    // Iterate over the array.
    for(int i = 0; i < n; i++){

        // If the current element is 0.
        if(A[i] == 0){

            // Increment the “count0” variable.
            count0++;
        }
    }

    // Iterate over the array from 0 to (“count0” - 1) 
    // and mark all the elements as 0.
    for(int i = 0; i < count0; i++){
        A[i] = 0;
    }

    // Iterate over the array from “count0” to (‘N’ - 1) 
    // and mark all the elements as 1.
    for(int i = count0; i < n; i++){
        A[i] = 1;
    }
}

Accepted Answer

Two Pointer Approach

We will put all the 0s to the left side. Hence all the 1s will be automatically pushed to the right side. For that, we will take two variables - one will traverse the array from the right and another from the left till they reach the same place. If the right one has 0 it will swap with the left one. Thus all the 0s will come towards the left side.

Algorithm:

Declare two integer variables “index0” and “index1”.
Set “index0” to 0 and “index1” to (‘N’ - 1).
Start a while loop with the condition: “index0” < “index1”.
- If A[index1] is 0.
  - Swap A[index1] with A[index0].
  - Increment “index0”.
- Else
  - Decrement “index1”.

Space Complexity: O(1)Explanation:

O(1).

Constant space is used.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

Since we are iterating over the array, the time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    where N is the size of the array.

*/

public class Solution {

  

    public static void sort0and1(int n, int[] A) {

    

        // Declare two integer variables index0 and index1.

        // Set index0 to 0 and index1 to (N - 1).

        int index0 = 0;

        int index1 = n - 1;

        

        // Start a while loop with the condition: index0 < index1.

        while(index0 < index1){



            // If A[index1] is 0.

            if(A[index1] == 0){



                // Swap A[index1] with A[index0].

                int temp = A[index0];

                A[index0] = A[index1];

                A[index1] = temp;



                // Increment index0.

                index0++;

            }



            // Else.

            else{



                // Decrement index1.

                index1--;

            }

        }

    

    }

}

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(1)

    where ‘N’ is the size of the array.
'''

def sort0and1(n, A):
    
    # Declare two integer variables “index0” and “index1”.
    # Set “index0” to 0 and “index1” to (‘N’ - 1).
    index0 = 0
    index1 = n - 1
    
    # Start a while loop with the condition: “index0” < “index1”.
    while(index0 < index1):

        # If A[index1] is 0.
        if(A[index1] == 0):

            # Swap A[index1] with A[index0].
            A[index0], A[index1] = A[index1], A[index0]

            # Increment “index0”.
            index0 += 1
    

        # Else.
        else:
            # Decrement “index1”.
            index1 -= 1

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    where ‘N’ is the size of the array.
*/

void sort0and1(int n, vector &A){
    
    // Declare two integer variables “index0” and “index1”.
    // Set “index0” to 0 and “index1” to (‘N’ - 1).
    int index0 = 0;
    int index1 = n - 1;
    
    // Start a while loop with the condition: “index0” < “index1”.
    while(index0 < index1){

        // If A[index1] is 0.
        if(A[index1] == 0){

            // Swap A[index1] with A[index0].
            swap(A[index0], A[index1]);

            // Increment “index0”.
            index0++;
        }

        // Else.
        else{

            // Decrement “index1”.
            index1--;
        }
    }
}

You are given an array ‘A’ of size ‘N’ containing only 0s and 1s. You have to sort the array by traversing the array only once.

For Example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Popular interview questions of Software Engineer