Dutch Flag Algorithm (DFA)

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.

  • worst time complexity for DFA: O(n)
  • 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.