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:

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

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.

```
 
```

//Java Program to Solve the Dutch National Flag Problem

```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
 
```
```
public class DutchNationalFlag {
```

    // Function to solve the Dutch National Flag problem

    static void dutchNationalFlag(int[] array){

```
        int low,high,middle,temp;
```
```
        low = middle = 0;
```
```
        high = array.length-1;
```
```
        while(middle<=high){
```
```
                if(array[middle] == 0)
```
```
                {
```
```
                    temp = array[low];
```

                    array[low] = array[middle];

```
                    array[mid] = temp;
```
```
                    low = low + 1;
```

                    middle  = middle + 1;

```
                }
```

                else if(array[middle] == 1)

```
                    middle++;
```
```
                else
```
```
                {
```
```
                    temp = array[high];
```

                    array[high] = array[middle];

                    array[middle] = temp;

```
                    high = high - 1;
```
```
                }
```
```
        }
```
```
    }
```
```
 
```

    // Function to read input and display the output

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int size;
```

        System.out.println("Enter the size of the array");

```
        try {
```

            size = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] array = new int[size];
```

        System.out.println("Enter array elements");

```
        int i;
```

        for (i = 0; i < array.length; i++) {

```
            try {
```

                array[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error occurred");

```
                return;
```
```
            }
```
```
        }
```

        System.out.println("The initial array is");

        for(i = 0;i < array.length; i++){

            System.out.print(array[i] + " ");

```
        }
```
```
        dutchNationalFlag(array);
```

        System.out.println("\nThe final array is");

        for(i = 0;i < array.length; i++){

            System.out.print(array[i] + " ");

```
        }
```
```
    }
```
```
}
```

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.

Subscribe Now: Java Programs Newsletter | Important Subjects Newsletters

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Replace Elements with Greatest Element on Right Side

» Next - Java Program to Find the Length of Longest Repeating Sequence in a String

Related Posts:

Practice Programming MCQs
Practice BCA MCQs
Check Java Books
Apply for Java Internship
Practice Information Technology MCQs

Recommended Articles: