Problem Statement
Given an array containing 0’s, 1’s and 2’s, Sort the array inplace. You can’t count the frequency of elements and refill the array.
The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem.
In-place: Do not use Extra Space.
Example:
Input: arr: [1, 1, 2, 0, 1, 0, 2, 1, 0] Output: [0, 0, 0, 1, 1, 1, 1, 2, 2]
Code
Java
C++
Python
class Innoskrit {
public static void sort(int[] arr) {
int zero = 0, one = 0, two = arr.length - 1;
while(one <= two) {
int element = arr[one];
if(element == 0) {
swap(arr, zero, one);
zero++;
one++;
} else if(element == 1) {
one++;
} else {
swap(arr, one, two);
two--;
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int arr[] = new int[] {1, 1, 2, 0, 1, 0, 2, 1, 0};
Innoskrit.sort(arr);
for(int x : arr) {
System.out.print(x + " ");
}
}
}
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static void sort(vector<int> &arr) {
int zero = 0, one = 0, two = arr.size() - 1;
while(one <= two) {
int element = arr[one];
if(element == 0) {
swap(arr, zero, one);
zero++;
one++;
} else if(element == 1) {
one++;
} else {
swap(arr, one, two);
two--;
}
}
}
private:
static void swap(vector<int> &arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
};
int main() {
vector<int> arr = {1, 1, 2, 0, 1, 0, 2, 1, 0};
Innoskrit::sort(arr);
for (int x : arr)
cout<<x<<" ";
return 0;
}
class Innoskrit:
@staticmethod
def sort(arr):
zero, one, two = 0, 0, len(arr) - 1
while one <= two:
element = arr[one]
if element == 0:
arr[zero], arr[one] = arr[one], arr[zero]
zero += 1
one += 1
elif element == 1:
one += 1
else:
arr[one], arr[two] = arr[two], arr[one]
two -= 1;
if __name__ == '__main__':
arr = [1, 1, 2, 0, 1, 0, 2, 1, 0]
Innoskrit.sort(arr)
print(arr)
Output:
[0, 0, 0, 1, 1, 1, 1, 2, 2]
Time and Space Complexity
Time Complexity: O(N)
Space Complexity: O(1)