Three way partitioning of an Array without changing the relative ordering
Given an array and a range [lowVal, highVal], partition the array around the range such that the array is divided into three parts.
- All elements smaller than lowVal come first.
- All elements in range lowVal to highVal come next.
- All elements greater than highVVal appear in the end.
- The relative ordering of numbers shouldn’t be changed.
Examples:
Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}, lowVal = 14, highVal = 20
Output: arr[] = { 1 5 4 2 3 1 14 20 20 54 87 98 32 }Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}, lowVal = 20, highVal = 20
Output: arr[] = { 1 14 5 4 2 3 1 20 20 54 87 98 32 }
Approach: This approach is based on using extra data structures to store the elements lesser than lowVal, in between lowVal and highVal, and elements greater than highVal. We will be using 3 queue for maintaining the original order of elements.
- Traverse the array one by one
- Insert the array elements into the respective queue one by one
- At the end,
- Pop out all the elements in queue 1 with elements lesser than lowVal
- Then Pop out all the elements in queue 2 with elements in between lowVal and highVal
- Then Pop out all the elements in queue 3 with elements greater than highVal.
Below is the implementation of the above approach:
C++
// C++ code to implement three way // partitioning of an array without // changing the relative ordering #include <bits/stdc++.h> using namespace std; // Function to do three way partitioning vector< int > pivotArray(vector< int >& nums, int lowVal, int highVal) { // Declaring 3 queues queue< int > before, same, after; // Traverse the array elements one by one for ( int i = 0; i < nums.size(); i++) { // If the element is // less than pivot range // insert it into queue before if (nums[i] < lowVal) before.push(nums[i]); // Else If the element is // in between pivot range // insert it into queue same else if (nums[i] > highVal) after.push(nums[i]); // Else If the element is // less than pivot range // insert it into queue after else same.push(nums[i]); } int k = 0; // Now insert all elements // in queue before and // insert into final vector while (before.size() > 0) { nums[k++] = before.front(); before.pop(); } // Now insert all elements // in queue same and // insert into final vector while (same.size() > 0) { nums[k++] = same.front(); same.pop(); } // Now insert all elements // in queue after and // insert into final vector while (after.size() > 0) { nums[k++] = after.front(); after.pop(); } // Return the final vector return nums; } // Driver code int main() { vector< int > arr = { 1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32 }; int lowVal = 20, highVal = 20; pivotArray(arr, lowVal, highVal); for ( int i = 0; i < arr.size(); i++) { cout << arr[i] << " " ; } return 0; } |
Java
// JAVA code to implement three way // partitioning of an array without // changing the relative ordering import java.util.*; class GFG { // Function to do three way partitioning public static int [] pivotArray( int [] nums, int lowVal, int highVal) { // Declaring 3 queues Queue<Integer> before = new LinkedList<>(); Queue<Integer> same = new LinkedList<>(); Queue<Integer> after = new LinkedList<>(); // Traverse the array elements one by one for ( int i = 0 ; i < nums.length; i++) { // If the element is // less than pivot range // insert it into queue before if (nums[i] < lowVal) before.add(nums[i]); // Else If the element is // in between pivot range // insert it into queue same else if (nums[i] > highVal) after.add(nums[i]); // Else If the element is // less than pivot range // insert it into queue after else same.add(nums[i]); } int k = 0 ; // Now insert all elements // in queue before and // insert into final vector while (before.size() > 0 ) { nums[k++] = before.poll(); } // Now insert all elements // in queue same and // insert into final vector while (same.size() > 0 ) { nums[k++] = same.poll(); } // Now insert all elements // in queue after and // insert into final vector while (after.size() > 0 ) { nums[k++] = after.poll(); } // Return the final vector return nums; } // Driver code public static void main(String[] args) { int arr[] = new int [] { 1 , 14 , 5 , 20 , 4 , 2 , 54 , 20 , 87 , 98 , 3 , 1 , 32 }; int lowVal = 20 , highVal = 20 ; pivotArray(arr, lowVal, highVal); for ( int i = 0 ; i < arr.length; i++) { System.out.print(arr[i] + " " ); } } } // This code is contributed by Taranpreet |
Python3
# Python 3 code to implement three way # partitioning of an array without # changing the relative ordering # Function to do three way partitioning def pivotArray(nums, lowVal, highVal): # Declaring 3 queues before = [] same = [] after = [] # Traverse the array elements one by one for i in range ( len (nums)): # If the element is # less than pivot range # insert it into queue before if (nums[i] < lowVal): before.append(nums[i]) # Else If the element is # in between pivot range # insert it into queue same elif (nums[i] > highVal): after.append(nums[i]) # Else If the element is # less than pivot range # insert it into queue after else : same.append(nums[i]) k = 0 # Now insert all elements # in queue before and # insert into final vector while ( len (before) > 0 ): nums[k] = before[ 0 ] k + = 1 before.pop( 0 ) # Now insert all elements # in queue same and # insert into final vector while ( len (same) > 0 ): nums[k] = same[ 0 ] same.pop( 0 ) k + = 1 # Now insert all elements # in queue after and # insert into final vector while ( len (after) > 0 ): nums[k] = after[ 0 ] k + = 1 after.pop( 0 ) # Return the final vector return nums # Driver code if __name__ = = "__main__" : arr = [ 1 , 14 , 5 , 20 , 4 , 2 , 54 , 20 , 87 , 98 , 3 , 1 , 32 ] lowVal = 20 highVal = 20 pivotArray(arr, lowVal, highVal) for i in range ( len (arr)): print (arr[i], end = " " ) # This code is contributed by ukasp. |
C#
// C# code to implement three way using System; using System.Collections; public class GFG{ // partitioning of an array without // changing the relative ordering // Function to do three way partitioning static int [] pivotArray( int [] nums, int lowVal, int highVal) { // Declaring 3 queues Queue before = new Queue(); Queue same = new Queue(); Queue after = new Queue(); // Traverse the array elements one by one for ( int i = 0; i < nums.Length; i++) { // If the element is // less than pivot range // insert it into queue before if (nums[i] < lowVal) before.Enqueue(nums[i]); // Else If the element is // in between pivot range // insert it into queue same else if (nums[i] > highVal) after.Enqueue(nums[i]); // Else If the element is // less than pivot range // insert it into queue after else same.Enqueue(nums[i]); } int k = 0; // Now insert all elements // in queue before and // insert into final vector while (before.Count > 0) { nums[k++] = ( int )before.Peek(); before.Dequeue(); } // Now insert all elements // in queue same and // insert into final vector while (same.Count > 0) { nums[k++] = ( int )same.Peek(); same.Dequeue(); } // Now insert all elements // in queue after and // insert into final vector while (after.Count > 0) { nums[k++] = ( int )after.Peek(); after.Dequeue(); } // Return the final vector return nums; } // Driver code static public void Main (){ int [ ] arr = { 1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32 }; int lowVal = 20, highVal = 20; pivotArray(arr, lowVal, highVal); for ( int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " " ); } } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code to implement three way // partitioning of an array without // changing the relative ordering // Function to do three way partitioning const pivotArray = (nums, lowVal, highVal) => { // Declaring 3 queues let before = [], same = [], after = []; // Traverse the array elements one by one for (let i = 0; i < nums.length; i++) { // If the element is // less than pivot range // insert it into queue before if (nums[i] < lowVal) before.push(nums[i]); // Else If the element is // in between pivot range // insert it into queue same else if (nums[i] > highVal) after.push(nums[i]); // Else If the element is // less than pivot range // insert it into queue after else same.push(nums[i]); } let k = 0; // Now insert all elements // in queue before and // insert into final vector while (before.length > 0) { nums[k++] = before[0]; before.shift(); } // Now insert all elements // in queue same and // insert into final vector while (same.length > 0) { nums[k++] = same[0]; same.shift(); } // Now insert all elements // in queue after and // insert into final vector while (after.length > 0) { nums[k++] = after[0]; after.shift(); } // Return the final vector return nums; } // Driver code let arr = [1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32]; let lowVal = 20, highVal = 20; pivotArray(arr, lowVal, highVal); for (let i = 0; i < arr.length; i++) { document.write(`${arr[i]} `); } // This code is contributed by rakeshsahni </script> |
1 14 5 4 2 3 1 20 20 54 87 98 32
Time Complexity: O(N), where N is the size of the array.
Auxiliary Space: O(N)
Contact Us