Wizard’s Question

Easy
0/40
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
Microsoft

Problem statement

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.

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 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
Sample Input 1:
2
5
2 3 4 5 1
5
2 1 3 4 4
Sample Output-1
1
4
Explanation for Sample Input 1:
For case 1:
    The segment will be [2, 3, 4, 5, 1], i.e. we take the whole array. There is no possible way to divide the array into two or more than two parts and still get the sorted array. Hence the answer will be 1.
For Case 2:
    The segments will be [2, 1], [3], [4], [4], as we divided the array into four parts, so our answer will be 4.
Sample Input 2:
2
4
4 3 2 1
5
2 1 4 5 3
Sample Output-2
1
2
Hint

 What are the 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 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’
Time Complexity

O(N * N * log(N)), where N is the length 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 length of the array.

 

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

Code Solution
(100% EXP penalty)
Wizard’s Question
Full screen
Console