One Pager Cheat Sheet

• The Dutch national flag problem requires sorting an array consisting of only 0s, 1s, and 2s in linear time and constant space.
• The time complexity for the worst case of the QuickSort algorithm is O(n^2) because it often chooses the last element as the pivot and keeps partitioning the same subarrays.
• Quick Sort is a divide-and-conquer algorithm which divides an array into three parts, recursively partitions them, and finally sorts the array in ascending order.
• The Dutch National Flag Problem is solved by using multiple pointers to expand "groups" over time by a series of swaps.
• We will swap elements in a given array with indices split into three "groups" to arrange the partitions, having the top group "grow downwards" and the bottom group "grow upwards".
• The Dutch National Flag Problem requires the middle to stay above the bottom, with its core conditional logic to be put together.
• We are swapping elements in-place and analyzing them with respect to the low, mid, and high indices to sort them into specific groupings, resulting in linear O(n) time complexity and constant O(1) space complexity.
• The Dutch National Flag Problem is solved by establishing three pointers -- low, mid, and high -- and using them to iterate through the array and swap elements to "wiggle" them to the right place.
• The Dutch National Flag algorithm uses one pointer and three boundary variables - low, mid, and high - to sort an array of 0, 1, 2 elements in linear time.
• We can apply bucket sorting with O(n) complexity and O(1) space complexity to solve this problem which uses 3 known elements (0, 1, and 2).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function swap(arr, first, second) {

  var temp = arr[first];

  arr[first] = arr[second];

  arr[second] = temp;

}

​

function dutchNatFlag(arr) {

  let low = 0;

  let mid = 0;

  let high = arr.length - 1;

​

  while (mid <= high) {

    if (arr[mid] === 0) {

      swap(arr, low++, mid++);

    } else if (arr[mid] === 2) {

      swap(arr, mid, high--);

    } else if (arr[mid] === 1) {

      mid++;

    }

  }

​

  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(

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.