General

No Comments

Sorting an Array Containing 0’s, 1’s, and 2’s

Sorting an array containing 0’s, 1’s, and 2’s is one of the most asked interview questions. In this article, we will explore the problem statement, discuss various approaches to solving it, and provide an optimised solution using the Dutch National Flag algorithm.

Problem Statement

Given an array of size n containing only the elements 0, 1, and 2, sort the array in ascending order. The solution should aim to sort the array in linear time, i.e., O(n), and with constant space, i.e., O(1).

Examples

	Input: [0, 1, 2, 0, 1, 2]
	Output: [0, 0, 1, 1, 2, 2]

	Input: [2, 0, 1]
	Output: [0, 1, 2]

Approaches

  1. Counting Sort

The simplest approach is to count the number of 0’s, 1’s, and 2’s in the array and then overwrite the array with the counted numbers in order. This approach requires two passes over the array: one for counting and another for overwriting.

Time Complexity: O(n)
Space Complexity: O(1)
  1. Dutch National Flag Algorithm

The Dutch National Flag algorithm, proposed by Edsger W. Dijkstra, is an optimal one-pass solution to this problem. This algorithm uses three-pointers to partition the array into three sections: one for 0’s, one for 1’s, and one for 2’s.

Time Complexity: O(n)
Space Complexity: O(1)

Step-by-Step Solution Using Dutch National Flag Algorithm

1. Initialize Pointers:

  • low: Points to the next position where a 0 should be placed.
  • mid: Current element being evaluated.
  • high: Points to the next position where a 2 should be placed.

2. Traverse the Array:

  • If the current element (arr[mid]) is 0, swap it with the element at low, and increment both low and mid.
  • If the current element is 1, just increment mid.
  • If the current element is 2, swap it with the element at high, and decrement high.

3. Continue Until mid Exceeds high:

  • The array is sorted once mid exceeds high.

Implementation in JavaScript

Here’s how you can implement the Dutch National Flag algorithm in JavaScript:

function sort012(arr) {
  let low = 0, mid = 0, high = arr.length - 1;

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

// Test cases
console.log(sort012([0, 1, 2, 0, 1, 2])); // Output: [0, 0, 1, 1, 2, 2]
console.log(sort012([2, 0, 1])); // Output: [0, 1, 2]
console.log(sort012([2, 2, 0, 1, 0, 1])); // Output: [0, 0, 1, 1, 2, 2]

Close Menu