Sort Array of 0s and 1s.

Easy
0/40
Average time to solve is 10m
profile
Contributed by
26 upvotes
Asked in companies
WalmartIon TradingHashedIn

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4
1 0 1 0 
6
0 1 1 0 0 0
Sample Output 1:
0 0 1 1
0 0 0 0 1 1
Explanation For Sample Output 1:
For the first test case, the sorted array will be [0 0 1 1].

For the second test case, the sorted array will be [0 0 0 0 1 1].
Sample Input 2:
2
10
0 1 1 0 1 0 1 1 0 0
8
1 1 1 0 0 1 0 1
Sample Output 2:
0 0 0 0 0 1 1 1 1 1
0 0 0 1 1 1 1 1
Hint

Count the number of 0s and 1s and accordingly create the sorted array.

Approaches (2)
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.
Time Complexity

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

 

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

Space Complexity

O(1).

 

Constant space is used.

Code Solution
(100% EXP penalty)
Sort Array of 0s and 1s.
Full screen
Console