Sort an array of 0s, 1s, and 2s — Dutch national flag problem

Navtosh

Published in

EnjoyAlgorithms

4 min readJun 9, 2020

Difficulty Level

Medium

Asked In

Amazon, Microsoft, SAP Labs

Two solutions Discussed

Brute Force approach — Double Traversal
Efficient approach — Single scan using three-way partitioning

Key takeaway after reading this blog

This is a special sorting problem that can be solved using O(n) time complexity. There is a lot of variation available to this problem.
This is a good interview problem where we optimize the solution using a single scan and three-pointers only.
This problem is a simple variation of the famous Dutch national flag problem.

Let’s understand the problem

Given an array a[] consisting of 0s, 1s, and 2s. Write a program to sort the array of 0’s, 1’s, and 2’s in ascending order.

Examples

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

Solution 1: Double Traversal (Brute Force approach)

The first approach that comes to mind is to simply count the number of 0’s, 1’s, and 2’s. Then, place all 0’s at the beginning of the array, followed by 1’s and 2's.

Algorithm Steps

Declare three variables count_zero, count_ones, and count_twos to store the respective frequencies of appearances of 0’s, 1’s, and 2’s in the array.
Traverse through the array and update the frequency of 0’s, 1’s, and 2’s.
Then, traverse the array again and replace the first count_zero places of the array with 0, the next count_ones places with 1, and the last count_twos places with 2.

Algorithm Pseudocode

Algorithm Analysis

Time complexity = Time complexity of counting the number of 0’s, 1’s, and 2’s + Time complexity of placing all 0’s, 1’s, and 2’s in the array = O(n) + O(n) = O(n).

As no extra space is required, the space complexity of the above code is O(1). The critical question: Can we solve this problem using a single scan? (Think!)

Solution 2: Single scan using three-way partitioning

Algorithm Idea

We can solve the problem using a single scan by maintaining the correct order of 0’s, 1’s, and 2’s using variables. Actually, we have three types of elements to be placed in sorted order. Therefore, we divide the given array into four sections using three-pointers. Let us name these pointers as low, mid, and high:

a[0…low-1]: only zeroes
a[low..mid-1]: only ones
a[mid…high]: unknown
a[high+1..n-1]: only twos

We can think of low and high as the range [low, high] for values in the middle partition. In other words, the middle partition will contain the values from pointer low to pointer high.

Algorithm Steps

Initialise three pointers low = 0, mid = 0 and high = n — 1.

Run a loop until mid<=high

If (a[mid] == 0), then swap the element with the element at index low and shrink the unknown range by doing low++ and mid++.
If (a[mid] == 1), then simply increment mid (mid++), thus further shrinking the unknown range.
If (a[mid] == 2), then swap it with an element at index high and decrement high (high — ). Then, again traverse the array from mid-index only, as the element at this index has not been considered yet. Think!

Algorithm Pseudocode

Algorithm Analysis

Time complexity: The time complexity of the above code is the time required to traverse the array, i.e., O(n).

Space complexity: As no extra space is required, the space complexity of the above code is O(1).

Possible questions by the Interviewer

Can we optimize the above code and reduce the number of swap operations?
Can we solve this problem using the two-pointers approach?
Is this algorithm stable? If not, how can we improve the algorithm and make it stable?
Why don’t we increase the value of mid if a[mid] == 2?
How can we modify the above code for a similar problem that involves sorting an array containing 0s, 1s, 2s, and 3s?
What is the name of the famous linear-time sorting algorithm? In what circumstances do we use this algorithm? Can we apply an idea similar to counting sort for the solution to the above problem?

Sort an array of 0s, 1s, and 2s — Dutch national flag problem

Difficulty Level

Asked In

Two solutions Discussed

Key takeaway after reading this blog

Let’s understand the problem

Solution 1: Double Traversal (Brute Force approach)

Algorithm Steps

Algorithm Pseudocode

Algorithm Analysis

Solution 2: Single scan using three-way partitioning

Algorithm Idea

Algorithm Steps

Algorithm Pseudocode

Algorithm Analysis

Possible questions by the Interviewer

Suggested problems to explore using single loop, two pointers approach

Written by Navtosh