Three Way Partition

Moderate

0/80

Average time to solve is 15m

Contributed by

30 upvotes

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

1
5 2 3
2 0 1 3 4

Sample Output 1 :

Correct

Explanation for Sample Output 1:

After modifying the array according to the given condition, we will get 0 1 2 3 4 .
Since this element array satisfies the required properties, so we will get output as Correct.

Sample Input 2 :

1
5 4 6
1 3 5 7 9

Sample Output 2 :

Correct

Hint 1

Hint 2

Try to use the simplest possible approach.

Approaches (2)

Approach 1

Approach 2

Sorting

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.

Time Complexity

O(N * logN), where N is the number of elements in the array.

Since the inbuilt sort function for any language is mainly Quicksort and Merge sort and the time complexity of these algorithms is O(N * logN).

Space Complexity

O(1), per test case.

We are using constant extra space.

(100% EXP penalty)

Three Way Partition

Console