Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Why don’t you give a try to solve the problem by yourself before reading the article from here are array Sort 0 1 2?

Please make sure you try at least once it will help you understanding more. If after reading you didn't understand then this blog will help you to understand the problem of sorting an array of 0's, 1's, and 2's.

The Dutch national flag problem is a problem in computer science programming proposed by Edsger Dijkstra. The flag of Netherland has three colours: white, red, and blue. Now you’re given balls of three colours which are arranged randomly in a line (count of balls doesn’t matter).

Now your task is to randomly arrange balls of three colours such that balls of the same colour are placed together while on the other hand if we compare it to another problem. You may see this problem at Google, Palantir, PayPal and Zillow.

Consider an array think like you have an array of n elements which consists of elements 0,1, and 2 and you have to make an arrangement such that array is sorted or in other words, all 0’s, 1’s, and 2’s are together.

Here, we will use the integers 0 for representing red colour, 1 for white and 2 to represent the colour blue respectively.

For example, Consider an array, A= [2,0,2,1,0,1,0,2].

After sorting array would become like this [0,0,0,1,1,2,2,2].

Image Source:- leetcode

One way of solving this problem is with the help of sorting algorithms such as merge-sort or quick-sort as we also know there are inbuilt sorting functions in C++/Java/Python which are hybrid of merge and insertion sort which would get us the final answer in a relatively fine way.

It has atime complexityof O(nlogn), where n is the number of total items in the array.

So the easier solution would involve iterating through the original array and count the number of colored objects and just overwriting the original array in a second pass.

For solving this problem, I would suggest you to brushing up on quicksort. If you remember, the partition step of quicksort has some interesting effects.

In the partition step, we choose a pivot element and all the elements smaller than it is shifted to the left of it and greater elements than the pivot element are placed to the right.

Don’t remember?

Don’t worry here’s a look at the algorithms.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Solution 1: Two-Pass algorithm

Image Source: ytimg.com

Example:

Array = [0, 1, 2, 0, 2, 1, 1]
Pivot Index = 1
Value at pivot index is 1.
Forward pass: (Searching to place items less than 1)
When, i = 0 [0, 1, 2, 0, 2, 1, 1] Swap index 0 with index 0
When, i = 1 [0, 1, 2, 0, 2, 1, 1] (no swap)
When, i = 2 [0, 1, 2, 0, 2, 1, 1] (no swap)
When, i = 3 [0, 0, 2, 1, 2, 1, 1] Swap index 1 with index 3
When, i = 4 [0, 0, 2, 1, 2, 1, 1] (no swap)
When, i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap)
When, i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap)
After backwards pass: (Searching to place items greater than 1)
When, i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap)
When, i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap)
When, i = 4 [0, 0, 2, 1, 1, 1, 2] Swap index 4 and index 6
When, i = 3 [0, 0, 2, 1, 1, 1, 2] (no swap)
When, i = 2 [0, 0, 1, 1, 1, 2, 2] Swap index 2 and index 5
When, i = 1 [0, 0, 1, 1, 1, 2, 2] (stop* as the array is sorted)

Using this idea we can solve this problem with 2 passes O(~2N) time complexity and O(1) space. Here’s the python code:

Solution 2: Three-Way Partitioning (Single pass)

So in the worst case, for each item, we need to do an extra logn amount of work to be able to complete the sort. And we know that the worst-case space complexity for the merge sort is O(n), which we don’t want.

Could you think of another approach that will help in solving the problem with one-pass using only constant space?

So the one thing that comes into our mind after solving the problem from the above approach is, “Can we have a more efficient algorithm than using these conventional sorting algorithms?”

The answer is YES. We can take advantage of the fact there are just 3 distinct values scattered in the array.

Let’s try to change that partition function such that our colours get organised in one pass.

Let’s try to analyse this situation as shown in the figure below:

Image Source: zunayed.dev

The idea is quite simple. Track and Swap:

First, we can start with the mid-value of the 3 values as a pivot.

From that pivot (middle) value, we can place values less than pivot in the left of the pivot.

Place values higher than pivot in the right of the pivot.

If they are equal to the pivot (middle) value, we do pretty much nothing.

We are going to swap array elements around so that we don’t have to use extra space.

For this, we are using 3-pointers as the name suggests there will be three-pointers low, mid, and high. With the help of “pointers”, we’ll be able to sort the array by swapping the value in constant time.

If you’re the lazy one and don’t want to learn any algorithm then there is a brute force approach for you, we know there are only 3 elements 0,1, and 2. This gives us a hint:

Start with declaring three variable assuming count0, count1, and count2 with initialising these with zero.

Now traverse the whole array once counting the no. of 0’s,1’s, and 2’s with increasing the particular count. After traversal of the array, you have a count of 0’s,1’s, and 2’s in the array.

Make a new variable say k=0 and traverse the array once again with updating the value of the array with 0’s first, then 1’s and finally with 2’s. So your final array will have sorted 0’s,1’s, and 2’s.

Here’s the C++ code for the same:

COMPLEXITY

As we can see there are n elements in the array and total two traversals are made so we know for traversal of an array consisting of n elements requires time complexity to be O(n) and same complexity for the second traversal so the overall complexity of the algorithm comes down to O(n) + O(n) = 2*O(n) and 2 is a constant so the overall time complexity is O(n) while we didn’t use any extra space, so the space complexity of the code is O(1).

An array is a group of related data elements kept in close proximity to one another in memory. The only way to access each data element directly is by using its index number, making it the most basic data structure.

What is Quick Sort?

The popular sorting algorithm known as Quicksort sorts an array of n elements with an average of n log n comparisons. It is a sorting algorithm that is both quick and very effective. This algorithm employs the strategy of "divide and conquer."

What is Merge Sort?

Merge sort sorts the elements using a divide-and-conquer strategy, it is comparable to the quick sort algorithm. One of the most well-liked and effective sorting algorithms is it. It divides the provided list into two equal parts, makes calls for each half, and then joins the two sorted halves.

This algorithm tells us about the quick-sort as it used there because that partitioning part is the core thing in quick-sort. But One thing we learnt here in this algorithm is to deal with time complexity like how we brought time complexity from O(nlogn) to O(n) using 3-partitioning.

Because we know one thing finding solution is not enough but finding an optimal solution is also necessary wherever possible.