Three way partitioning of an array around a given range

Problem Statement

You are given an array of integers and a range of lowValue and highValue. The problem “Three way partitioning of an array around a given range” asks to partition the array such that array will be divided into three parts. The partitions of the arrays will be:

1. Elements of the first partition will be lesser than the lowValue,
2. Next partition such that elements lies within the given range will be in this partition and the
3. Numbers greater than the highValue will be the third partition of the array.

Example

arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30

2 5 1 12 4 9 23 76 56 45 87

Explanation

lowValue is 15, such that the numbers in the left side will be less than the lowValue.

The range is between 15 and 30, 23 is the number that lies between this range

highValue is 30, all numbers greater than the highValue will be on the right side.

Algorithm

1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
    1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
    2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
    3. Else increase the value of i by 1.
3. Print the array.

Explanation

We have given an integer array and a range of lowValue and highValue. We have to arrange the array or partition the array. Such that all the possible numbers of the array which are less than the lowValue will be on the left side of the array. And the number of the array which lies between the range of the array will be next in the array. And the next values will be the numbers which are greater than the highValue will be the last.

We will be traversing the array, from the 0^th index to the last index. But before that, we have declared some variable and initialize it with the 0 and the last index of the array respectively. In swapping whenever the value lower than the lowValue is found, the operation will be performed on the startingValue and whenever the value greater than the highValue found, then the operation will be performed at endingValue. We will traverse the array and check if the current array element is less than the given lowValue if true then swap the current value of the array and the array first position value. This value we will keep track of the starting point and other value will keep the track of ending indexes for swapping the elements, another swap will be done if the element is found greater than the value of current array element. Then comes the endingValue, index at which the element is swapped with the current element. If none of the condition satisfies means the number lies within the given range then we do not change it. After the traversal completes, we have the desired array. We just need to print the array.

Code

C++ code to solve Three way partitioning of an array around a given range

#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int startingValue = 0, endingValue = n-1;

    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[startingValue++]);

        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);

        else
            i++;
    }
}

int main()
{
    int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 15, 30);

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

2 5 1 12 4 9 23 76 56 45 87

Java code to solve Three way partitioning of an array around a given range

class ThreeWayPartition
{
    public static void getPartition(int[] arr, int lowValue, int highValue)
    {
        int n = arr.length;

        int startingValue = 0, endingValue = n-1;

        for(int i = 0; i <= endingValue;)
        {
            if(arr[i] < lowValue)
            {

                int temp = arr[startingValue];
                arr[startingValue] = arr[i];
                arr[i] = temp;
                startingValue++;
                i++;
            }
            else if(arr[i] > highValue)
            {

                int temp = arr[endingValue];
                arr[endingValue] = arr[i];
                arr[i] = temp;
                endingValue --;
            }
            else
                i++;
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

        getPartition(arr, 15, 30 );

        for (int i=0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");

        }
    }
}

2 5 1 12 4 9 23 76 56 45 87

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Since we have traversed over the array elements the time complexity is linear.

Space Complexity

O(1) as no extra space is required. The algorithm itself is in-place algorithm and is updating the initial given array. Thus the space complexity of the algorithm is constant while the program is linear.