SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Dutch National Flag Visualizer

lo marks where the next 0 goes, hi where the next 2 goes. mid scans the unknown part in between.

Start the Dutch National Flag simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Three zones: 0s before lo, 1s from lo to mid, 2s after hi. Between mid and hi is still unknown. [2, 0, 2, 1, 1, 0, 1, 2, 0]
  2. a[mid] is 2.
  3. It is 2. Swap it to hi and move hi left. mid stays: the new value is unchecked. [0, 0, 2, 1, 1, 0, 1, 2, 2]
  4. a[mid] is 0.
  5. It is 0. Swap it to lo, then move lo and mid right.
  6. a[mid] is 0.
  7. It is 0. Swap it to lo, then move lo and mid right.
  8. a[mid] is 2.
  9. It is 2. Swap it to hi and move hi left. mid stays: the new value is unchecked.
  10. a[mid] is 2.
  11. It is 2. Swap it to hi and move hi left. mid stays: the new value is unchecked. [0, 0, 1, 1, 1, 0, 2, 2, 2]
  12. a[mid] is 1.
  13. It is 1, already in the middle zone. Move mid right.
  14. a[mid] is 1.
  15. It is 1, already in the middle zone. Move mid right.
  16. a[mid] is 1.
  17. It is 1, already in the middle zone. Move mid right.
  18. a[mid] is 0.
  19. It is 0. Swap it to lo, then move lo and mid right. [0, 0, 0, 1, 1, 1, 2, 2, 2]
  20. Done. 0s, then 1s, then 2s, in a single pass.

Try it with your own input →

Dutch national flag in Java, Python, C++, C and JavaScript

void sortColors(int[] a) {
  int lo = 0, mid = 0, hi = a.length - 1;
  while (mid <= hi) {
    if (a[mid] == 0) swap(a, lo++, mid++);
    else if (a[mid] == 1) mid++;
    else swap(a, mid, hi--);
  }
}
def sort_colors(a):
    lo, mid, hi = 0, 0, len(a) - 1
    while mid <= hi:
        if a[mid] == 0:
            a[lo], a[mid] = a[mid], a[lo]
            lo += 1; mid += 1
        elif a[mid] == 1:
            mid += 1
        else:
            a[mid], a[hi] = a[hi], a[mid]
            hi -= 1
void sortColors(vector<int>& a) {
  int lo = 0, mid = 0, hi = (int)a.size() - 1;
  while (mid <= hi) {
    if (a[mid] == 0) swap(a[lo++], a[mid++]);
    else if (a[mid] == 1) mid++;
    else swap(a[mid], a[hi--]);
  }
}
void sortColors(int a[], int n) {
  int lo = 0, mid = 0, hi = n - 1, t;
  while (mid <= hi) {
    if (a[mid] == 0) { t = a[lo]; a[lo++] = a[mid]; a[mid++] = t; }
    else if (a[mid] == 1) mid++;
    else { t = a[mid]; a[mid] = a[hi]; a[hi--] = t; }
  }
}
function sortColors(a) {
  let lo = 0, mid = 0, hi = a.length - 1;
  while (mid <= hi) {
    if (a[mid] === 0) { [a[lo], a[mid]] = [a[mid], a[lo]]; lo++; mid++; }
    else if (a[mid] === 1) mid++;
    else { [a[mid], a[hi]] = [a[hi], a[mid]]; hi--; }
  }
}

In an interview

LeetCode 75, Sort Colors: sort an array of 0s, 1s and 2s in one pass.

After swapping with hi, do not move mid. The value that came from hi has not been checked yet.

More patterns