Problem: Sort an Array of 0s, 1s, and 2s

Given an array/list ARR consisting of integers where each element is either 0, 1, or 2, your task is to sort this array in increasing order.

Input:

The input starts with an integer ‘T’ representing the number of test cases.
For each test case:
The first line contains a positive integer ‘N’, denoting the number of elements in the array.
The second line contains ‘N’ space-separated integers, which are the elements of the array.

Output:

For each test case, output the sorted array of ‘N’ space-separated integers on a new line.

Example:

Input:

2
4
0 2 1 1
5
2 1 0 0 1

Output:

0 1 1 2
0 0 1 1 2

Explanation:

For the first test case, the sorted array is [0, 1, 1, 2].
For the second test case, the sorted array is [0, 0, 1, 1, 2].

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 5000

0 ≤ ARR[i] ≤ 2

Time limit: 1 sec

Note:

You are not required to print anything; the output handling has already been managed. Simply implement the function to sort the array.

Question

Problem: Sort an Array of 0s, 1s, and 2s

Given an array/list ARR consisting of integers where each element is either 0, 1, or 2, your task is to sort this array in increasing order.

Input:

The input starts with an integer ‘T’ representing the number of test cases. 
 For each test case:
 The first line contains a positive integer ‘N’, denoting the number of elements in the array.
 The second line contains ‘N’ space-separated integers, which are the elements of the array.

Output:

For each test case, output the sorted array of ‘N’ space-separated integers on a new line.

Example:

Input:

Output:

0 1 1 2
0 0 1 1 2

Explanation:

For the first test case, the sorted array is [0, 1, 1, 2].
For the second test case, the sorted array is [0, 0, 1, 1, 2].

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 5000
0 ≤ ARR[i] ≤ 2
Time limit: 1 sec

Note:

You are not required to print anything; the output handling has already been managed. Simply implement the function to sort the array.

Accepted Answer

The task is to sort an array of 0s, 1s, and 2s in increasing order.

Use a three-pointer approach to partition the array into three sections: 0s, 1s, and 2s.
Initialize three pointers: low, mid, and high. low points to the start of the array, mid points to the current element being processed, and high points to the end of the array.
While mid <= high, if ARR[mid] is 0, swap ARR[low] and ARR[mid], increment low and mid. If ARR[mid] is 1, increment mid. If ARR[mid] is 2, swap ARR[mid] and ARR[high], decrement high.
Repeat the above step until mid <= high.
The array will be sorted in increasing order.

Problem: Sort an Array of 0s, 1s, and 2s

Input:

Output:

Example:

Input:

Output:

Explanation:

Constraints:

Note:

Paytm SDE-2 interview questions & answers

Popular interview questions of SDE-2