Sort an Array of 0s and 1s

Sort an array that contains only 0s and 1s, ensuring that the array is traversed only once to achieve the sorting.

Input:

T = number of test cases
N = size of the array for each test case
A = array containing only 0s and 1s

Output:

The sorted array for each test case, maintaining the order of 0s followed by 1s.

Example:

For the given array:

[0, 1, 1, 1, 0, 0, 1]

The output should be:

[0, 0, 0, 1, 1, 1, 1]

Constraints:

1

Question

Sort an array that contains only 0s and 1s, ensuring that the array is traversed only once to achieve the sorting.

T = number of test cases
N = size of the array for each test case
A = array containing only 0s and 1s

The sorted array for each test case, maintaining the order of 0s followed by 1s.

For the given array:

[0, 1, 1, 1, 0, 0, 1]

The output should be:

[0, 0, 0, 1, 1, 1, 1]

The array should be sorted in place, meaning you do not need to return a new array, simply modify the given array.

Accepted Answer

Use two pointers approach to traverse the array and swap 0s and 1s to achieve sorting in place.

Initialize two pointers, one at the beginning and one at the end of the array.
Move the left pointer until it encounters a 1, and move the right pointer until it encounters a 0.
Swap the elements at the left and right pointers, and continue this process until the pointers meet.
The array will be sorted with 0s on the left and 1s on the right.

Popular interview questions of Software Engineer