Dutch National Flag Approach

An effective method proposed to sort an array which consists of three different variations of components

Before breaking the iceberg of sorting algorithms and the realms of minimal time and space complexity
Few interview questions pull out unique scenario-based questions that do not involve you inhaling data structures or OOP concepts.

One such question is the infamous DNF problem, which involves sorting three elements 0, 1, and 2. A common scenario is sorting an array of integers representing different colours, such as red, white, and blue.

Understanding the Dutch National Flag Algorithm

The Dutch National Flag algorithm is to solve sorting problems where the array or list needs to be separated into three parts. For example, consider an array where:

• 0 represents red

• 1 represents white

• 2 represents blue

Our goal is to sort this array such that all reds come first, followed by whites, and then blues. The algorithm achieves this in a single pass through the array, making it highly efficient with a time complexity of O(n) and a space complexity of O(1).

Pseudocode

function DNF(nums: array of numbers):
    initialize low to 0
    initialize mid to 0
    initialize high to length of nums - 1

    while mid <= high do:
        if nums[mid] is 0:
            swap nums[low] and nums[mid]
            increment low by 1
            increment mid by 1
        else if nums[mid] is 1:
            increment mid by 1
        else: // nums[mid] is 2
            swap nums[high] and nums[mid]
            decrement high by 1

Partitioning Idea:

• Think of the array as divided into three sections:

  • All 0s (left section)

  • All 1s (middle section)

  • All 2s (right section)

• We use three pointers (low, mid, and high) to manage these sections dynamically.

Pointer Roles:

• low points to where the next 0 should go.

• mid scans through each element to determine its category (0, 1, or 2).

• high points to where the next 2 should go.

How it Works:

• As we traverse the array using the mid pointer:

  • If nums[mid] is 0:

    • Swap it with the element at low (ensuring 0 moves to the left).

    • Increment both low and mid since the new value at mid is confirmed.

  • If nums[mid] is 1:

    • Just move mid forward, as 1 is already correctly positioned.

  • If nums[mid] is 2:

    • Swap it with the element at high (ensuring 2 moves to the right).

    • Decrement high to reduce the size of the section containing 2s.

    • mid does not move, as we need to check the new value at mid.

Result:

By moving and swapping elements using these simple rules, the array is sorted in-place in a single pass, with all 0s, followed by 1s, and then 2s.

---

Conclusion:

The primary advantage of using this approach is the one-pass technique and the minimal space complexity it requires, and the alternative to this is the Counting Sort Algorithm, which also takes a time complexity of O(n) but a high space complexity.