Last Updated: 16 Feb, 2021

Three Way Partition

Moderate

Asked in company

Problem statement

You are given an array consisting of N positive integers and a range [A, B], where A and B are two integers. You have to modify the array such that the following conditions are satisfied:

1. All the elements of the array strictly smaller than ‘a’ should come first.
2. All the elements of the array between the range [a, b] should come next.
3. All the elements of the array strictly greater than ‘b’ should come last.

Input Format :

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains three space-separated integers N, A, B, denoting the size of the array, the first element of the range, and the second element of the range [a, b] respectively.

The second line of each test case contains N space-separated integers representing the elements of the array.

Output Format :

The output of the test case will be “Correct” if you have modified the array correctly else it will be “Incorrect” without quotes. 
The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 5000
0 <= arr[i] <= 10^9
0 <= a, b <= 10^9

Solve now

Approaches

01 Approach

The simplest possible approach will be to sort the array.
So after applying the algorithm, we will get one possible solution, we can simply return the array.

Solve now

02 Approach

Since sorting is trivial and we are also given that there are only three distinct integers in the array, we can use three-pointers to solve this problem. We are going to use a technique that is an application of the famous Dutch national flag theorem.

The algorithm will be as follows:

Let ‘low’ = 0 and ‘high’ = n - 1 initially.
For index = 0 to index <= high do the following:
- If ARR[ index ] < a:
  - We know that this element should be on the lower end of the array so we can swap ‘ARR[ index ]’ with ‘ARR[ low ]’.
  - Increment ‘low’ and ‘index’ by 1 i.e do low += 1 and index += 1.
- Else if ‘ARR[ index ]’ > b:
  - We know that this element should be on the last of the array, so we swap ‘ARR[ index ]’ and ‘ARR[ high ]’
  - Decrement ‘high’ by 1 i.e. do high -= 1.
- Else increment ‘index’ by 1 i.e. do index += 1 as we know that this element should be in the middle of the array.

Solve now