Partition Array

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in companies
MicrosoftGrabMakeMyTrip

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
6
8 3 1 4 9 10
6
5 4 3 2 1 10
Sample Output 2
4
5
Explanation:
For the first test case, ‘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.

For the second test case, ‘arr’ = [5, 4, 3, 2, 1, 10], this array can be partitioned at index ‘4’ so the left array is [5, 4, 3, 2, 1] and the right array is [10]. Hence the answer is 5.
Sample Input 2:
2
3
3 1 4
4
1 2 3 4 5
Sample Output 2:
2
1
Hint

Find the minimum and maximum of left and right arrays for each index.

Approaches (2)
Simple 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
Time Complexity

O(N), Where N is the number of elements in the array.

 

We are iterating over the array three times, Hence the overall time complexity is O(3*N) = O(N).

Space Complexity

O(N), Where N is the number of elements in the array.

 

We are maintaining two arrays of N size. Hence the overall space complexity is O(2*N) = O(N).

 

Code Solution
(100% EXP penalty)
Partition Array
Full screen
Console