Break and Merge

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
MicrosoftAdobe

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
2 1 0 3
5
1 0 2 3 4
Sample Output 1
2
4
Explanation for Sample Input 1:
For case 1:
    The array will be divided into two parts [2, 1, 0], [3]. No more subparts are possible, which give the sorted array. Hence answer is 2.
For Case 2:
    The subarrays will be [1, 0], [2], [3], [4]. Hence answer is 4.
Sample Input 2:
2
5
4 3 2 1 0
3
0 1 2
Sample Output 2:
1
3
Hint

Find positions of each element in the final array ?

Approaches (2)
Brute Force

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’
Time Complexity

O(N * N * log(N)), where N is the size of the array.

 

We are sorting the ‘cur’ array a total of ‘N’ times. Hence the overall complexity is O(N * N * log(N)).

Space Complexity

O(N), where N is the size of the array.

 

We are creating three arrays of length ‘N’. Hence the overall complexity is O(N).

Code Solution
(100% EXP penalty)
Break and Merge
Full screen
Console