Arrays: Three way partitioning of an array around a given range

Problem Statement:

Given an array and 2 values [a, b], you need to create a partition such that:

1. Elements of the first partition will be lesser than “a”
2. Next partition such that elements lies within the given range will be in this partition
3. Numbers greater than the “b” will be the third partition of the array

Example:

Input: arr = [1, 14, 51, 12, 4, 2, 54, 20, 87, 98, 3, 1, 32]
a = 14, b = 54
Output: arr = [1, 12, 4, 2, 3, 1, 14, 51, 20, 32, 54, 87, 98]
First part is [1, 12, 4, 2, 3, 1]
Second part is [14, 51, 20, 32]
Third part is [54, 87, 98]

Solution:

The solution in very simple, explained in below steps:

1. Take 2 pointer pointing at start and end of the array.

2. Now traverse the array, and check if the current value is less than “a”, then swap arr[i] and arr[start_index] and increment both start_index and i by 1

3. Else if the current array element is greater than “b”, swap arr[i] and arr[end_index], increase the value of i and decrease value of end_index by 1

4. else increase the value of i by 1

Time Complexity: O(n)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int start_index = 0, endingValue = n-1;
    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[start_index++]);
        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);
        else
            i++;
    }
}
int main()
{
    int arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 10, 20);
    
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}

Output:

1 5 4 2 1 3 14 20 20 98 87 32 54

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *