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 partitioningvector<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 codeint 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 orderingimport 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 partitioningdef 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 codeif __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 wayusing 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> |
Output
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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!