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.

54%
Solution Ratio

Samin_SieyamEarliest,

defaltFastest, 0.3s

YouKnowWhoLightest, 78 MB

NirjhorShortest, 594B

Toph uses cookies. By continuing you agree to our Cookie Policy.