Sort 0 1 2 Problem Statement

Given an integer array arr of size 'N' containing only 0s, 1s, and 2s, write an algorithm to sort the array.

Input:

The first line contains an integer 'T' representing the number of test cases. Each test case consists of two lines. The first line contains an integer 'N', the size of the array. The second line contains 'N' space-separated integers, the elements of the array.

Output:

For each test case, output the sorted array as space-separated integers in a new line.

Example:

Input: 2 5 0 2 1 2 0 3 2 1 0 Output: 0 0 1 2 2 0 1 2

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 5 * 10⁵

0 ≤ arr[i] ≤ 2

Time Limit: 1 sec

Note:

Try to solve the problem using a single scan over the array. You need to modify the array in-place and do not return anything.

Question

Sort 0 1 2 Problem Statement

Given an integer array arr of size 'N' containing only 0s, 1s, and 2s, write an algorithm to sort the array.

Input:

The first line contains an integer 'T' representing the number of test cases. Each test case consists of two lines. The first line contains an integer 'N', the size of the array. The second line contains 'N' space-separated integers, the elements of the array.

Output:

For each test case, output the sorted array as space-separated integers in a new line.

Example:

Input:
2
5
0 2 1 2 0
3
2 1 0
Output:
0 0 1 2 2
0 1 2

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 5 * 10⁵
0 ≤ arr[i] ≤ 2
Time Limit: 1 sec

Note:

Try to solve the problem using a single scan over the array. You need to modify the array in-place and do not return anything.

Accepted Answer

Sort an array of 0s, 1s, and 2s in linear time complexity.

Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.
Iterate through the array and swap elements based on the values encountered.
Maintain left pointer for 0s, right pointer for 2s, and current pointer for traversal.
Example: If current element is 0, swap it with element at left pointer and increment both pointers.

Accepted Answer

function sort0_1_2(arr) {
  let current = 0;
  let zeroPos = 0;
  let twoPos = arr.length - 1;

  while (current <= twoPos) {
    if (arr[current] === 0) {
      [arr[current], arr[zeroPos]] = [arr[zeroPos], arr[current]];
      current++;
      zeroPos++;
    }else if(arr[current] === 1) {
        current++
    }else if (arr[current] === 2) {
      [arr[current], arr[twoPos]] = [arr[twoPos], arr[current]];
      twoPos -= 1;
    }
  }
  return arr;
}