Dutch National Flag Problem in Java

«
»

This is the Java Program to Solve the Dutch National Flag Problem.

Problem Description

Given an array of 0’s, 1’s and 2’s, all the elements in the random order, sort the array in linear time, without using extra space. This is known as the Dutch National Flag problem.
Example:

advertisement

Array = [1 0 2 2 0 1]

Output
Array = [0 0 1 1 2 2]

Problem Solution

The idea here is to divide the array into three regions such that the starting region contains all the zeroes, the next season contains all the ones and the final region contains all the zeroes. Start from the beginning of the array and check if the element is zero or two, if it is then interchange it with the first one, if it is a one continue iterating.

Program/Source Code
advertisement
advertisement

Here is the source code of the Java Program to Solve the Dutch National Flag Problem. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Solve the Dutch National Flag Problem
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class DutchNationalFlag {
  8.     // Function to solve the Dutch National Flag problem
  9.     static void dutchNationalFlag(int[] array){
  10.         int low,high,middle,temp;
  11.         low = middle = 0;
  12.         high = array.length-1;
  13.         while(middle<=high){
  14.                 if(array[middle] == 0)
  15.                 {
  16.                     temp = array[low];
  17.                     array[low] = array[middle];
  18.                     array[mid] = temp;
  19.                     low = low + 1;
  20.                     middle  = middle + 1;
  21.                 }
  22.                 else if(array[middle] == 1)
  23.                     middle++;
  24.                 else
  25.                 {
  26.                     temp = array[high];
  27.                     array[high] = array[middle];
  28.                     array[middle] = temp;
  29.                     high = high - 1;
  30.                 }
  31.         }
  32.     }
  33.  
  34.     // Function to read input and display the output
  35.     public static void main(String[] args) {
  36.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  37.         int size;
  38.         System.out.println("Enter the size of the array");
  39.         try {
  40.             size = Integer.parseInt(br.readLine());
  41.         } catch (Exception e) {
  42.             System.out.println("Invalid Input");
  43.             return;
  44.         }
  45.         int[] array = new int[size];
  46.         System.out.println("Enter array elements");
  47.         int i;
  48.         for (i = 0; i < array.length; i++) {
  49.             try {
  50.                 array[i] = Integer.parseInt(br.readLine());
  51.             } catch (Exception e) {
  52.                 System.out.println("An error occurred");
  53.                 return;
  54.             }
  55.         }
  56.         System.out.println("The initial array is");
  57.         for(i = 0;i < array.length; i++){
  58.             System.out.print(array[i] + " ");
  59.         }
  60.         dutchNationalFlag(array);
  61.         System.out.println("\nThe final array is");
  62.         for(i = 0;i < array.length; i++){
  63.             System.out.print(array[i] + " ");
  64.         }
  65.     }
  66. }
Program Explanation

1. In the function dutchNationalFlag(), we take three variables low, mid and high.
2. low and mid are initialized to zero, whereas high is initialized to array.length – 1.
3. Now using the loop while (mid <= high), we check the array elements at index mid, using a switch statement.
4. If the element is zero according to case 0, then we interchange the elements at index low and mid, and increment both low and mid.
5. If the element is one according to case 1, we increment mid.
6. Finally, if the element is two according to case 2, we swap the element at mid and high, along with decrementing high.

advertisement

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple test Case):
 
Enter the size of the array
6
Enter array elements
1
0
2
2
0
1
The initial array is
1 0 2 2 0 1 
The final array is
0 0 1 1 2 2 
 
Case 2 (Simple test Case - another example):
 
Enter the size of the array
8
Enter array elements
2
2
0
0
0
1
1
1
The initial array is
2 2 0 0 0 1 1 1 
The final array is
0 0 0 1 1 1 2 2

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.