# Min operations to empty an array by erasing any rising subsequence

0
9

Given array A[] of dimension N, the duty is to search out the variety of operations to empty the array by performing the next operation a number of occasions. In a single operation select any strictly rising subsequence and delete it from A[].

Examples:

Enter: A[] = {2, 1, 4, 5, 3}
Output: 2
Clarification: Following operations are carried out to empty the array:

• Selecting rising subsequence {2, 4, 5} and eradicating it from A[], A[] turns into {1, 3}
• Selecting rising subsequence {1, 3} and eradicating it from A[], A[] turns into empty.

Enter: A[] = {0, 0, 0, 0}
Output:  4

Strategy: The thought is to make use of a Precedence Queue knowledge construction to unravel this downside.

Iterate over the array and maintain inserting new component to precedence queue, if given component is inserted at non-starting place than delete component simply earlier to that place.

Beneath are the steps for the above method:

• Create precedence queue pq[] utilizing a multiset container to retailer the array parts in sorted order.
• Iterate from 0 to N – 1.
• For every iteration, insert the present component in pq[].
• For every iteration, search the present component in pq[].
• If the present component is on the preliminary place within the precedence queue, transfer to the following iteration, else erase the earlier component within the precedence queue.
• Return the scale of pq[] which would be the reply.

Beneath is the code for the above method:

## C++

 `#embody ` `utilizing` `namespace` `std;` ` `  `int` `findMinOp(``int` `A[], ``int` `N)` `{` ` `  `    ` `    ``multiset<``int``> pq;` ` `  `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` ` `  `        ` `        ` `        ``pq.insert(A[i]);` ` `  `        ` `        ` `        ``auto` `it = pq.discover(A[i]);` ` `  `        ` `        ` `        ` `        ``if` `(it == pq.start())` `            ``proceed``;` ` `  `        ``it--;` ` `  `        ` `        ` `        ``pq.erase(it);` `    ``}` ` `  `    ` `    ` `    ``return` `pq.dimension();` `}` ` `  `int` `major()` `{` `    ``int` `A[] = { 2, 1, 4, 5, 3 };` `    ``int` `N = ``sizeof``(A) / ``sizeof``(A[0]);` ` `  `    ` `    ``cout << findMinOp(A, N) << endl;` ` `  `    ``return` `0;` `}`

Time Complexity: O(NlogN)
Auxiliary House: O(N)

Associated Articles :