C++ Program for Three Way Partitioning - O(n) solution

Three way partitioning refers to divide an array in three parts such as:
1. All the elements smaller than given lower_value should appear first.
2. All the elements between given lower_value and higher_value should come next.
3. All the elements greater than given higher_value should appear in the end.

C++ Program for the three way partitioning of the array is given below. The time and space complexity of the given solution is O(n) and O(1) respectively.

PROGRAM:

```#include <bits/stdc++.h>
using namespace std;

void threeWayPartition(vector<int> &A,int lowVal,int highVal)
{

int start=0,end=A.size()-1;
for(int i=0;i<=end;){

if(A[i]<lowVal){

int temp=A[start];
A[start]=A[i];
A[i]=temp;
i++;
start++;
}

else if(A[i]>highVal){

int temp=A[end];
A[end]=A[i];
A[i]=temp;
end--;
}
else
{
i++;
}

}

}

int main(){

int n;

cout<<"\nEnter the total number of elements: \n";
cin>>n;

cout<<"\nEnter the elements:\n";
int num;

std::vector<int> A;

for(int i=0;i<n;i++){
cin>>num;
A.push_back(num);
}

int lowVal,highVal;

cout<<"\nEnter the lowVal and highVal respectively: ";
cin>>lowVal>>highVal;

cout<<"\n";

threeWayPartition(A,lowVal,highVal);
cout<<"\nThe container after three way partitioned: \n";
for(int i=0;i<A.size();i++) {
cout<<A[i]<<" ";
}
cout<<"\n";
return 0;
}```

OUTPUT: