Last Updated: 25 Nov, 2021

Partition Array

Moderate

Asked in companies

Solve now

Problem statement

You are given an array, ‘arr’, your task is to partition the array into such a way that, that all the elements in the left half of the array are smaller than or equal to all the elements in the right half the array. Each partition should have at least one element. You have to return the smallest length of the left partition possible.

Note:

The left half of the array must be the smallest possible.
If there is no partition return the size of the array.

For example:

You are given, ‘arr’ = [8, 3, 1, 4, 9, 10], this array can be partitioned at index ‘3’ so the left array is [8, 3, 1, 4] and the right array is [9, 10]. Hence the answer is 4.

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the size of the array.

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

Output Format:

For each test case print a single integer representing the number of elements in the left half of the array.

For each test case, print a single integer.

Constraints:

1 <= T <= 10
1 <= N <= 10^6
1 <= arr[i] <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we can observe that the array will only be valid if the maximum element of the left array is smaller than the minimum element of the right array.

In the given array we have to find the first index i where the largest element from 0 to i is smaller than the smallest element from i + 1 to N - 1. To do this we can create a maxLeft array and minRight array where maxLeft[i] will store the maximum element till i from left and minRight[i] will store the minimum element till i from right.

Algorithm:

Create two arrays equal to the size of ‘arr’, ‘maxLeft’ and ‘minRight’
Set maxLeft[0] as array[0] and last element of minRight as last element of ‘arr’
Iterate i from 1 to size of arr -1
- Set maxLeft[i] as maximum of maxLeft[i - 1] and arr[i]
Iterate i from size of ‘arr’ - 2 to 0
- Set minRigth[i] as minimum of minRight[i + 1] and arr[i]
Iterate i from 0 to size of ‘arr’ - 1
- If maxLeft[i] is less than minRight[i + 1]
  - Return i + 1
Return size of the array

Solve now

02 Approach

In this approach, we use the same idea that the largest element in the left array should be smaller than the smallest element in the right array.

To do this in one iteration we can do as follows

Iterate over the array
Update the maximum element found till now
If the current element is less than the leftmax, set leftmax element as the maximum element till now and mark, mark the current number as the end of the left array.

Algorithm:

Set partitionIndex as 0
Set localMaximum and overallMax as arr[0]
Iterate i from 0 to size of arr
- Set num as arr[0]
- Set overallMax as the maximum of num and overallMax.
- If num is less than localMaximum
  - Set localMaximum as overallMax
  - Set partitionIndex as i
Return parititionIndex + 1

Solve now