AlgoDaily - Dutch National Flag Problem

Dutch National Flag Problem (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Google, Palantir, Paypal, Zillow, Coinbase, Walmart Labs, Benchling, Intel, Cornerstone, and Baidu.

This problem is named the "Dutch national flag problem" because the flag of the Netherlands is comprised of the colors red, white, and blue in separate parts. Although we won't be using colors, the premise of the challenge is to develop a sorting algorithm that performs some form of separations of three kinds of elements.

To simplify things, we'll use 0s, 1s, and 2s.

Given an array consisting of only 0s, 1s, and 2s, sort the elements in linear time and constant space.

JAVASCRIPT

1const arr = [2, 0, 1, 0, 2]
2dutchNatFlag(arr)
3// [0, 0, 1, 2, 2]

Constraints

Length of the array <= 100000

xxxxxxxxxx
​
 
var assert = require('assert');
​
function swap(arr, first, second) {}
​
function dutchNatFlag(arr) {
  // Fill in this method
  return arr;
}
​
dutchNatFlag([2, 2, 2, 0, 0, 0, 1, 1]);
​
try {
  assert.deepEqual(dutchNatFlag([2, 0, 1, 0, 2]), [0, 0, 1, 2, 2]);
​
  console.log(
    'PASSED: assert.deepEqual(dutchNatFlag([2, 0, 1, 0, 2]), [0, 0, 1, 2, 2]);'
  );
} catch (err) {
  console.log(err);
}
​
try {
  assert.deepEqual(dutchNatFlag([0, 1, 2]), [0, 1, 2]);
​
  console.log(
    'PASSED: ' + 'assert.deepEqual(dutchNatFlag([0, 1, 2]), [0, 1, 2]);'
  );

OUTPUT

Results will appear here.