Hello everyone. The reason for this blog is that I haven't seen much talk about solutions to this type of problem here, so I'd like to provide a basic introduction of it to this community.
Let's first look at the naive solution to this problem.
The naive solution to this problem for an array-like data structure $$$A$$$ is, for each element $$$A_i$$$, iterate through the entire data structure, and if you find an element $$$A_j$$$ satisfying $$$A_j < A_i$$$, move onto the next element $$$A_{i + 1}$$$. If you don't, you have your answer, $$$A_i$$$.
This is how one might implement such a solution in python:
Unfortunately, this works in $$$O(n^2)$$$ time. How can we optimize this? We can use dynamic programming.
For a $$$1$$$-indexed array-like data structure $$$A$$$ of length $$$n$$$, let's define $$$dp_i$$$ as the minimum element that appears in the substructure $$$A[i...n]$$$.
It is clear that the minimum element that appears in $$$A[n...n]$$$ is simply $$$A_n$$$. Therefore, our base case is $$$dp_{n} = A_n$$$. For indices $$$1...n - 1$$$, we can construct our answer using this recurrence relation: $$$dp_i = min(A_i, dp_{i + 1})$$$. It is clear that the answer to our problem is $$$dp_1$$$.
This works in $$$O(n)$$$ time and $$$O(n)$$$ space. A trick to reduce the space complexity is to notice that the recurrence relation doesn't need anything other than $$$dp_{i + 1}$$$ when calculating $$$dp_i$$$. Therefore, instead of creating a $$$dp$$$ array, we can simply update the value of $$$dp_{i + 1}$$$ using a variable.
Here is how you might implement this in python:
That is all. I hope you learned something!
Basically what you are saying is prefix sums, but the sums is minimums. Normal prefix sums pre-calculation is O(n^2), but that can be optimized to O(n) with a process called Dynamic Programming!
However, as Dynamic Programming can be a very advanced topic to some, just use a heap or balancing binary search tree (priority queue / set) to do it in O(nlogn)! This is very helpful for people who don't want to do DP if avoidable. O(nlogn) works 99% of the time if O(n) works.
After second thought, we can apply a lazy propagated segment tree to do this quite easily in O(nlogn) time :)
Minimum is easy but how to find maximum?
it is a bit trickier