Sort an Array of 0's, 1's, and 2's Problem Statement

Given an integer array ARR of size 'N' containing only the values 0, 1, and 2, the task is to sort this array.

The goal is to achieve the sorting in a single pass through the array.

Example:

Input:

T = 2
N = 5
ARR = [0, 2, 1, 2, 0]
N = 3
ARR = [0, 1, 0]

Output:

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

Note:

The solution must involve iterating over the array just once.

Constraints:

1

Question

Given an integer array ARR of size 'N' containing only the values 0, 1, and 2, the task is to sort this array.

The goal is to achieve the sorting in a single pass through the array.

T = 2
N = 5
ARR = [0, 2, 1, 2, 0]
N = 3
ARR = [0, 1, 0]

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

The solution must involve iterating over the array just once.

1 <= T <= 10
1 <= N <= (5 * 10⁵)
0 <= ARR[i] <= 2
You need to sort the given array/list itself. No need to return or print anything explicitly.

Accepted Answer

Sort an array of 0's, 1's, and 2's in a single pass.

Use three pointers to keep track of 0's, 1's, and 2's positions while iterating through the array.
Swap elements based on the current element's value and the pointers.
Achieve sorting in a single pass by moving the pointers accordingly.

Top Capgemini Engineering Software Engineer interview questions & answers