Last Updated: 26 Oct, 2021
Wizard’s Question
Easy
Asked in company
Your dream is to join the magic school, and this time you have been selected to give the entrance examination. The head of the school, the great wizard, is taking your exam personally. He knows you like sorting, so he will ask you ‘T’ sorting questions. He will give you an array of length ‘N’ consisting of integers to sort in each question. But there is a catch; he asked you to divide the array into the maximum number of consecutive segments such that all segments are disjoint, and every index of the array must be included in some segment. Then you sort all the segments individually and merge them, forming a non-decreasing array of length ‘N’.
E.g: let an array be [2, 1, 4, 5, 3]. We can divide this into two parts: [2, 1, 4] , [5, 3] and after sorting both the part individually we get : [1, 2, 4] , [3, 5], then we merge them forming the final array [1, 2, 4, 3, 5].
Note: The above example is not optimal as the final array is not sorted.
For each question, you have to tell the great wizard the maximum number of segments in which you can break the array and still get the final array sorted.
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 segments in which you can break the array and still get the final array sorted.
Constraints -
1<= ‘T’ <= 5
1<= ‘N’ <= 10^5
0<= A[i] <= 10^9 i ∈ (1,N)
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 left of the ‘ith’ index in the final sorted array.
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.
If the maximum of all the values to its left is less or equal to the minimum value to its right, then we can end a segment at the ‘ith’ index. I.e max(a1, a2, .. , ai) <= min(a(i + 1), … , an). The condition is true because if the minimum value on the right (Let’s say ‘ar’) to index ‘i’ is smaller than the largest value from the left (let’s say ‘al’). Suppose we end the segment at the index ‘i’. We can’t bring the smaller value ‘ar’ before, the larger value ‘al’. The final array might look like [..., al], [ar, ....] since ‘al’ > ‘ar’. Hence the array will not be sorted.
Algorithm:
- Create an array ‘rightMin’ of length ‘N + 1’, and initialize the last value to ‘INT_MAX’.
- Iterate using a for loop from i = ‘N - 1’ to ‘0’.
- Update rightMin[i] to min(rightMin[i + 1], A[i]).
- Create two variables, ‘mx’ and ‘ans’, and initialize both of them to 0.
- Iterate using a for loop from i = ‘0’ to ‘N - 1’.
- Update ‘mx’ to max(mx, A[i]).
- If mx <= rightMin[i + 1].
- Increment the ‘ans’ by 1.
- Print ‘ans’.