Given an array A[] of N integers, the duty is to seek out the lexicographically smallest subsequence of the array by deleting all of the occurrences of precisely one integer from the array.
Examples:
Enter: N = 5, A[] = {2, 4, 4, 1, 3}
Output: {2, 1, 3}
Rationalization: All attainable subsequences of the array
after eradicating precisely one integer are :
On deleting 2: {4, 4, 1, 3}
On deleting 4: {2, 1, 3}
On deleting 1: {2, 4, 4, 3}
On deleting 3: {2, 4, 4, 1}
Lexicographically smallest amongst these is {2, 1, 3}Enter: N = 6, A[] = {1, 1, 1, 1, 1, 1}
Output: {}
Strategy: To resolve the issue comply with the beneath remark:
Commentary:
It may be noticed simply that to make a subsequence of an array lexicographically smallest, first factor which is bigger than its subsequent factor should be eliminated.
Based mostly on the above remark, the steps talked about beneath may be adopted to reach on the resolution:
- Iterate by means of the array.
- At every iteration evaluate the present factor with the following factor.
- Whether it is better than the following factor, break the loop and delete all of the occurrences of the present factor.
- Else, if the iteration completes with out breaking the loop, which means the array is sorted in rising order. In such case, delete all of the occurrences of the final factor of the array.
Under is the implementation of the above method.
C++
|
|
Time Complexity: O(N)
Auxiliary Area: O(1)
