For subtask 1:
For subtask 1, we can keep an array and can traverse the whole array for minimum and maximum. Worst case complexity will be O(n2).

For subtask 2:
For subtask 2, we can keep a multiset and add/erase dataset with a log factor. As, set is already sorted, we can find minimum and maximum in O(1). So, worst case complexity will be O(n log(n)).

For subtask 3:
As the removal is from back, we don't need to consider smaller elements while finding maximum element & larger elements while finding the minimum. How?
Lets, we have A = [5], then adding 1, 2, 3, 4, 5 etc don't have an effect on maximum. The maximum is still 5 after addition or removal from the back until we have to remove 5. So, instead of adding new element in the back, we can add current maximum, i.e. 5. If a value greater than 5 comes then we'll start adding the larger value from now on. For example, we have [5, 1, 2, 3, 4, 5, 7] to add one after another. Our maximum array will be [5, 5, 5, 5, 5, 7]. To find maximum we have to check the last element of the array.

We have to do the same for the minimum. Let's think we have A = [2], then adding 2, 3, 4, 5 etc don't have an effect on minimum. The minimum is still 2 after addition or removal from the back until we have to remove 2. So, instead of adding new element in the back, we can add current minimum, i.e. 2. If a value less than 2 comes then we'll start adding the smaller value from now on. For example, we have [2, 3, 4, 5, 1] to add one after another. Our minimum array will be [2, 2, 2, 2, 1]. To find minimum we have to check the last element of the array.

So to do this, we need a data structure that can remove element in O(1) from the back/top of the array. We can use stack for this. We need two separate stacks for minimum and maximum. The addition and finding max/min is done in O(1), so we can solve this problem in input time.

Statistics

56% Solution Ratio
Samin_SieyamEarliest, Jun '20
Sarwar82Fastest, 0.3s
YouKnowWhoLightest, 78 MB
NirjhorShortest, 594B
Toph uses cookies. By continuing you agree to our Cookie Policy.