Three-Way Partitioning of an Array Without Changing the Relative Ordering

In this article, we will do a three-way partitioning of an array containing N integers.

The approach is to use three queues. Each of these queues will be used to store the elements of one of the parts. After that, we can get the elements of each part from their respective queues without changing the relative order of the elements

Problem Statement

Given an array containing N integers and a range [LOW, HIGH], we need to partition the array into three parts such that

• Elements less than LOW comes first

• Elements greater than LOW and lower than HIGH come next.

• Elements greater than HIGH come at the end.

• The relative ordering of elements is preserved

Sample Examples

Input

arr = {3,1,5,10,3,7,2,5,6,8}, LOW = 3, HIGH = 7

Output

1 2 3 5 3 7 5 6 10 8

Explanation

Here, the elements less than 3 appear first, then the elements between 3 and 7 appear and elements greater than 7 appear last. The relative ordering of elements is preserved.

Input

arr = {10,9,8,7,6,5,4,3,2,1}, LOW = 5, HIGH = 8

Output

4 3 2 1 8 7 6 5 10 9

Explanation

Here, the elements less than 5 appear first, then the elements between 5 and 8 appear and elements greater than 8 appear last. The relative ordering of elements is preserved.

Input

arr = {4,3,3,5,6,3,100,321,45,54,5,6,1,2,3}, LOW = 5, HIGH = 10

Output

4 3 3 3 1 2 3 5 6 5 6 100 321 45 54

Explanation

Here, the elements less than 5 appear first, then the elements between 5 and appear and elements greater than 7 appear last. The relative ordering of elements is preserved.

Approach 1

In this approach, we will use three queue data structures to store the elements in the three parts, i.e., lesser that LOW, between LOW and HIGH, greater that HIGH. This will also maintain the original order of the elements.

Algorithm

• Step 1 Traverse the array elements.

• Step 2 Insert the elements in the respective queues.

• Step 2.1 Insert the element in queue 1 if it is lesser than LOW.

• Step 2.2 Insert the element in queue 2 if it is in between LOW and HIGH.

• Step 2.3 Insert the element in queue 3 if it is greater than HIGH.

• Step 3.1 Pop out all the elements from queue 1 and add these to the answer array.

• Step 3.2 Pop out all the elements from queue 2 and add these to the answer array.

• Step 3.3 Pop out all the elements from queue 3 and add these to the answer array.

• Step 4 Return the answer array.

Example

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> ThreeWayPartition(vector<int> &arr,int LOW,int HIGH){
   queue<int> q1,q2,q3;
   vector<int> ans;
   for(int i=0;i<arr.size();i++){
      if(arr[i]<LOW)q1.push(arr[i]);
      else if(arr[i]>=LOW && arr[i]<=HIGH)q2.push(arr[i]);
      else q3.push(arr[i]);
   }
   while(!q1.empty()){
      ans.push_back(q1.front());
      q1.pop();
   }
   while(!q2.empty()){
      ans.push_back(q2.front());
      q2.pop();
   }
   while(!q3.empty()){
      ans.push_back(q3.front());
      q3.pop();
   }
   return ans;
}
int main(){
   vector<int> arr = {4,3,3,5,6,3,100,321,45,54,5,6,1,2,3};
   int LOW = 5 , HIGH=10;
   vector<int> ans = ThreeWayPartition(arr,LOW,HIGH);
   for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
   cout<<'\n';
}

Output

4 3 3 3 1 2 3 5 6 5 6 100 321 45 54 

Time complexity O(N), where N is the size of the array

Space complexity O(N), to store the elements of the array