Last Updated: 29 Oct, 2021
Break and Merge
Moderate
Asked in companies
Given an array of ‘N’ integers which contains all numbers in the range [0, N-1] exactly once. John wants to sort this array, but sorting a large array is a difficult task for him. So he will break this array into ‘K’ disjoint subarrays and sort them individually. After sorting all ‘K’ subarrays, he will put them together and obtain the complete sorted array.
E.g: let an array be [1, 0, 4, 2, 3]. He can divide this into two subarrays: [1, 0] , [4, 2, 3] and after sorting both the subarrays individually he get : [0, 1] , [2, 3, 4], then he put them together and obtain final array [0, 1, 2, 3, 4].
Your task is to find the maximum possible value of ‘K’ such that it is possible to sort the original array by breaking it into ‘K’ subarrays.
Input Format:
The first line contains ‘T’, denoting the number of tests.
For each Test :
The first line contains an integer ‘N’, denoting the length of the array.
The second line contains an array ‘A’ of length ‘N’.
Output Format:
For each test, print an integer, denoting the maximum number of subarrays in which he can break the array and still get the final array sorted.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
0 <= A[i] < N i ∈ (1,N)
All elements A[i] are unique.
Time Limit: 1 sec
Approaches
Approach: Since we want our final array to be sorted, all the values in the initial array must reach their position in the sorted array. So if we end a segment at the ‘ith’ index, then all of the values to the left of the ‘ith’ index in the initial array must be equal to the values in the final sorted array at respective indices.
Algorithm:
- Create a copy of the initial array, ‘copy’ and sort it.
- Create two empty vectors, ‘cur’ and ‘req’.
- Create a variable ‘ans’, and initialize it to 0.
- Iterate using a for loop from i = ‘0’ to ‘N - 1’.
- Append copy[i] to ‘req’.
- Append A[i] to ‘cur’.
- Sort ‘cur’
- If cur == req.
- Increment the ‘ans’ by 1.
- Print ‘ans’
Approach: Let’s check when we can end the segment at the ‘ith’ index.
We know that the final array should look like [0, 1, 2 …… N-1], by which it’s observed that the maximum element in the prefix of length ‘x’ is value ‘x’ itself. Though all elements are unique, it can be concluded that if the maximum of any prefix is ‘p’ then [0, 1…. p-1] are also covered and the array can be divided at this position.
Algorithm:
- Create two variables, ‘mx’ and ‘ans’, and initialize both of them to 0.
- Iterate using a for loop from index i = ‘0’ to ‘N - 1’.
- Update ‘mx’ to max(mx, A[i]).
- If mx == i.
- Increment the ‘ans’ by 1.
- Print ‘ans’.