Let’s answer #3

Dutch Flag Algorithm

Aman Agarwal
Dec 29, 2020 · 2 min read

An introduction to the Dutch Flag Algorithm.

Photo by Markus Spiske on Unsplash

Dutch Flag Algorithm (DFA) is one of the most basic and important algorithms for arrays. It is used to segregate an array consisting of 3 numbers in linear time complexity.

The worst time complexity for DFA is O(n) and the space complexity for the algorithm is O(1). The problem statement is as follows:

An array consisting of 0s, 1s, and 2s is provided to you. The task is to write a function that segregates all the numbers together. The order can be anything.

Let's assume that the provided array A is
A = [1, 2, 0, 1, 2, 0, 1, 2, 0]
and the output expected is
A = [2, 2, 2, 0, 0, 0, 1, 1, 1]

To solve the problem, we need to first select the order. For this example, let's select 2,1,0.
Now we need to have 3 pointers namely start, end, and P, pointing to three different indices of the array.

The start will denote the first index of the middle element i.e 0 over here. The End will denote the last index of the middle element and pointer P will be used to traverse the array.

The loop will run while the P is not equal to End. As the P traverses, if P encounters 2, it will swap it with start and increment the start. Similarly, if P encounters 1, it will swap it with end and decrement end. The code is as follows:-

For a better understanding of the algorithm, write the stack trace on paper, and make sure you go through all the steps.

If you have any queries or you want me to cover any other algorithm, feel free to comment down the article.

Stay tuned for more such algorithms and concepts.

Find the best tutorials and courses for the web, mobile…

Quick Code
Aman Agarwal

Written by

A human trying to explore the world using a Developer’s Lens

Quick Code

Find the best tutorials and courses for the web, mobile, chatbot, AR/VR development, database management, data science, web design and cryptocurrency. Practice in JavaScript, Java, Python, R, Android, Swift, Objective-C, React, Node Js, Ember, C++, SQL & more.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store