ArraysMedium

Sort an array of 0's, 1's and 2's

Problem Statement:Given an array nums consisting of only 0, 1, or 2. Sort the array in non-decreasing order. The sorting must be done in-place, without making a copy of the original array.

JavaScript Solution & Complexity Analysis

Run & test in browser
JavaScript Lab Sandbox
/*
Problem Statement -> Given an array nums consisting of only 0, 1, or 2. Sort the array in non-decreasing order. The sorting must be done in-place, without making a copy of the original array.

Approach 1 -> Use any optimized sorting algorithm.

Approach 2 -> Count the number of 0, 1, 2 and then replace the original array value with the number of 0 then 1 and at last with 2.

Approach 3 (Dutch National Flag Algo) -> it states three condition, everything between [0....low-1] -> 0 extreme left, [low....mid-1] -> 1 and [high+1.....n-1] -> 1 extreme right 
*/

let testCase1 = [0, 1, 2, 0, 1, 2], testCase2 = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1];

function sort012Approach1(arr) {
  /*
    T.C -> O(nlogn)
    S.C -> O(1)
  */
  return arr.sort();
};

console.log("Test Case 1 Approach 1:", sort012Approach1(testCase1));
console.log("Test Case 2 Approach 1:", sort012Approach1(testCase2));


function sort012Approach2(arr) {
  /*
    T.C -> O(4N)
    S.C -> O(1)
  */
  let count0 = 0, count1 = 0, count2 = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0) {
      count0++;
    } else if (arr[i] === 1) {
      count1++;
    } else if (arr[i] === 2) {
      count2++
    }
  }

  for (let i = 0; i < count0; i++) {
    arr[i] = 0;
  }

  for (let i = count0; i < count0 + count1; i++) {
    arr[i] = 1;
  }

  for (let i = count0 + count1; i < count0 + count1 + count2; i++) {
    arr[i] = 2;
  }

  return arr;
};

console.log("Test Case 1 Approach 2:", sort012Approach2(testCase1));
console.log("Test Case 2 Approach 2:", sort012Approach2(testCase2));


function sort012Approach3(arr) {
  let low = 0, mid = 0, high = arr.length - 1;
  while (mid <= high) {
    if (arr[mid] === 0) {
      [arr[mid], arr[low]] = [arr[low], arr[mid]];
      mid++;
      low++;
    } else if (arr[mid] === 1) {
      mid++;
    } else {
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
    }
  }
  return arr;
};

console.log("Test Case 1 Approach 3:", sort012Approach3(testCase1));
console.log("Test Case 2 Approach 3:", sort012Approach3(testCase2));
Console Output
Click "Run Code" above to execute and view output...