Sort an array of 0s, 1s and 2s (Dutch National Flag Problem)

The problem is to sort an array of 0s, 1s, and 2s in linear time without using any extra space. This is known as the Dutch National Flag problem proposed by Edsger W. Dijkstra. Given an array consisting of only 0s, 1s, and 2s, the task is to arrange the array in ascending order.

Input-Output Examples

Example 1:

  • Input: [0, 1, 2, 0, 1, 2]
  • Output: [0, 0, 1, 1, 2, 2]

Example 2:

  • Input: [2, 0, 1]
  • Output: [0, 1, 2]

Example 3:

  • Input: [1, 0, 0, 2, 1, 2, 1, 0]
  • Output: [0, 0, 0, 1, 1, 1, 2, 2]

Approach:

To solve this problem efficiently, we use the Dutch National Flag algorithm. The idea is to keep three pointers to divide the array into three sections:

  1. Elements less than 1.
  2. Elements equal to 1.
  3. Elements greater than 1.

Steps to implement:

  1. Initialize three pointers: low to the beginning, mid to the beginning, and high to the end of the array.
  2. Iterate through the array with the mid pointer.
  3. If the element at mid is 0, swap it with the element at low, and increment both low and mid.
  4. If the element at mid is 1, move the mid pointer to the right.
  5. If the element at mid is 2, swap it with the element at high, and decrement high.

Technique

  • Three-way partitioning using three pointers.

C++ program to sort an array of 0s, 1s and 2s

cpp
#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        switch (nums[mid]) {
            case 0:
                swap(nums[low++], nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums[mid], nums[high--]);
                break;
        }
    }
}

int main() {
    vector<int> nums = {0, 1, 2, 0, 1, 2};
    sortColors(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Java program to sort an array of 0s, 1s and 2s

java
public class DutchNationalFlag {
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            switch (nums[mid]) {
                case 0:
                    swap(nums, low++, mid++);
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(nums, mid, high--);
                    break;
            }
        }
    }

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

    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 0, 1, 2};
        sortColors(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

Python program to sort an array of 0s, 1s and 2s

python
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

# Example usage
nums = [0, 1, 2, 0, 1, 2]
sortColors(nums)
print(nums)

By following this approach, you can sort an array of 0s, 1s, and 2s efficiently in linear time. This method ensures that the problem is solved with optimal time complexity and minimal space usage.

DSA

8513

339

Related Articles