Post
Ask Question

Explaining Dutch National Flag problem

Dutch National Flag problem efficiently sorts an array containing only 0s, 1s, and 2s. This approach sorts the array in a single pass with a time complexity of O(n) and a space complexity of O(1). It uses three-pointers to partition the array into three sections: one for 0s, one for 1s, and one for 2s.

public void SortColors(int[] nums)
{
    int low = 0, mid = 0, high = nums.Length - 1;

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

private void Swap(int[] nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

Initialization

  • We use three pointers: low, mid, and high.
  • low Starts at the beginning of the array and will track the position to place the next 0.
  • mid Also starts at the beginning and will traverse the array.
  • high Starts at the end of the array and will track the position to place the next 2.

Traversal and Sorting

  • We iterate through the array with the mid pointer.
  • If nums[mid] is 0, we swap it with the element at low and increment both low and mid. This ensures that all 0s are moved to the beginning.
  • If nums[mid] is 1, we simply move the mid pointer forward, as 1s are already in the correct position.
  • If nums[mid] is 2, we swap it with the element at high and decrement high. This ensures that all 2s are moved to the end. We do not increment mid in this case because the swapped element needs to be checked.

Termination

  • The loop continues until mid surpasses high, ensuring that all elements are sorted correctly.

This algorithm is efficient with a time complexity of O(n) and a space complexity of O(1), making it optimal for this problem.

Here's a step-by-step explanation:

Initialization

  • We use three pointers: low, mid, and high.
  • low starts at the beginning of the array and will track the position to place the next 0.
  • mid also starts at the beginning and traverses the array.
  • high starts at the end of the array and will track the position to place the next 2.

Traversal and Sorting:

  • We iterate through the array with the mid pointer.
  • If nums[mid] is 0, we swap it with the element at low and increment both low and mid. This ensures that all 0s are moved to the beginning.
  • If nums[mid] is 1, we simply move the mid pointer forward, as 1s are already in the correct position.
  • If nums[mid] is 2, we swap it with the element at high and decrement high. This ensures that all 2s are moved to the end. We do not increment mid in this case because the swapped element needs to be checked.

Termination:

  • The loop continues until mid surpasses high, ensuring that all elements are sorted correctly.

Let's take an example array: [0, 0, 1, 1, 2, 2]

Step-by-Step Process

  1. Initial State

    • Array: [2, 0, 2, 1, 1, 0]
    • low = 0, mid = 0, high = 5

  2. First Iteration (mid = 0)

    • nums[mid] is 2.
    • Swap nums[mid] with nums[high].
    • Decrement high.
    • Array: [0, 0, 2, 1, 1, 2]
    • low = 0, mid = 0, high = 4

  3. Second Iteration (mid = 0)

    • nums[mid] is 0.
    • Swap nums[mid] with nums[low].
    • Increment both low and mid.
    • Array: [0, 0, 2, 1, 1, 2]
    • low = 1, mid = 1, high = 4

  4. Third Iteration (mid = 1)

    • nums[mid] is 0.
    • Swap nums[mid] with nums[low].
    • Increment both low and mid.
    • Array: [0, 0, 2, 1, 1, 2]
    • low = 2, mid = 2, high = 4

  5. Fourth Iteration (mid = 2)

    • nums[mid] is 2.
    • Swap nums[mid] with nums[high].
    • Decrement high.
    • Array: [0, 0, 1, 1, 2, 2]
    • low = 2, mid = 2, high = 3

  6. Fifth Iteration (mid = 2)

    • nums[mid] is 1.
    • Increment mid.
    • Array: [0, 0, 1, 1, 2, 2]
    • low = 2, mid = 3, high = 3

  7. Sixth Iteration (mid = 3)

    • nums[mid] is 1.
    • Increment mid.
    • Array: [0, 0, 1, 1, 2, 2]
    • low = 2, mid = 4, high = 3

Termination

  • The loop terminates because mid (4) is greater than high (3).

Final Sorted Array

  • [0, 0, 1, 1, 2, 2]


Similar Articles