0% completed
Introduction to Array Notes
Kadane's Algorithm Notes
Maximum Subarray Sum
Flip Bits
Maximum subarray sum after K concatenation
Maximum Sum Rectangle
Dutch National Flag Algorithm
0% completed
Dutch National Flag Algorithm Notes
Sort 0 1 2
Quicksort using the Dutch national flag algorithm
0% completed
Searching and Sorting Notes
Search In Rotated Sorted Array
Form a Triangle
First and Last Position of an element in Sorted Array
Count Smaller or Equal elements in array
Algorithm to find best insert position in sorted array
0% completed
Introduction to Arrays Notes
Prefix and Suffix Sum Notes
Sum of Infinite Array
XOR Query
Product of Array except self
Count all sub-arrays having sum divisible by k
0% completed
Pair Sum
Valid Pairs
Max Product Count
Selling Stock
Non-Decreasing Array
Longest Consecutive Sequence
Second largest element in the array
Print the array after K operations
Minimum Number of Platforms
Majority Element - II
Data Structures & Algorithms
Report an issue
Dutch National Flag Algorithm Notes

Dutch National Flag Algorithm

 

Problem Statement

Given an array consisting of only 0s, 1s and 2s, sort the array.


Naive Approach:

Simply sort the array with the help of sorting algorithms like Merge Sort, Quick Sort. This gives a time complexity of O(N*logN), where N is the number of elements in the array.


Two-Pass Algorithm:

The solution involves iterating through the original array and counting the number of 0s, 1s, and 2s, and just overwriting the original array in a second pass. The only disadvantage is that we need to traverse the array twice to get a sorted array.


Steps:

  • Traverse the array once and keep track of the count of 0s, 1s and 2s encountered.
  • Now traverse the array again and overwrite the array starting from the beginning, first with 0s, then 1s, and finally all 2s.

 

Pseudocode:

 

/*
	array of size N from 0 to N-1 is considered        
*/
function sort012(arr, N)
	
	//	Initialize the cnt0, cnt1 and cnt2 variables to 0.
	cnt0 = 0
	cnt1 = 0
	cnt2 = 0

	// 	Count the number of 0s, 1s and 2s
	for idx = 0 to N-1
		if arr[idx] == 0
			cnt0 += 1
		else if arr[idx] == 1
			cnt1 += 1
		else 
			cnt2 += 1

	// 	Now overwrite the array from the beginning
	for idx = 0 to N-1
		if cnt0 > 0
			arr[idx] = 0
			cnt0 -= 1
		else if cnt1 > 0
			arr[idx] = 1
			cnt1 -= 1
		else 
			arr[idx] = 2
			cnt2 -= 1

 

Time complexity: O(N), where N is the number of elements in the array, as we traverse the array twice only.

Space complexity: O(1), as no extra space is required.

 

Dutch National Flag algorithm or Three-way partitioning

 

The Dutch National Flag algorithm or three-way partitioning algorithm allows sorting the array consisting of 0s, 1s, and 2s in a single traversal only and in constant space.


Steps:

  • Maintain three indices low = 0, mid = 0, and high = N-1, where N is the number of elements in the array.
    1. The range from 0 to low denotes the range containing 0s.
    2. The range from low to mid denotes the range containing 1s.
    3. The range from mid to high denotes the range containing any of 0s, 1s, or 2s.
    4. The range from high to N-1 denotes the range containing 2s.
  • The mid pointer denotes the current element, traverses the array while mid<=high i.e we have exhausted the search space for the range which can contain any of 0s, 1s, or 2s.
    1. If A[mid] == 0, swap A[mid] and A[low] and increment low and mid pointers by 1.
    2. If A[mid] == 1, increment the mid pointer by 1.
    3. If A[mid] == 2, swap A[high] and A[mid] and increment mid by 1 and decrement high by 1.

The resulting array will be a sorted array containing 0s, 1s, and 2s.


Pseudocode:

 

/*
	array of size N from 0 to N-1 is considered        
*/
function DNF(arr, N)

	//	Initializing low, mid and high pointers
	low = 0
	mid = 0
	high = N-1

	while mid <= high
		/* 
        	Check if arr[mid] == 0, swap arr[low] and arr[mid], increment mid and 
          	low pointers
		*/
		if arr[mid] == 0
			swap(arr[mid],arr[low])
			low += 1
			mid += 1
	
		//	Check if arr[mid] == 1, increment mid pointer
		else if arr[mid] == 1
			mid += 1

		/* 
        	Check if arr[mid] == 2, swap arr[mid] and arr[high], decrement high pointer
 		*/
		else if arr[mid] == 2
			swap(arr[mid],arr[high])
			high -= 1

 

Time complexity: O(N), where N is the number of elements in the array, as we sort the array in a single traversal only.

Space complexity: O(1), as no extra space is required.