Daily bit(e) of C++ | Maximum area between boundaries
Daily bit(e) of C++ #315, Common interview problem: Maximum area between boundaries.
Today, we will look at a common C++ interview problem: Maximum area between boundaries.
Given information about the height of a boundary at each position as std::vector<int64_t>, determine the maximum area formed between any two boundaries.
The area is the minimum height of the two boundaries multiplied by the distance.
For example, for the input {1,2,5,3,2,12,1,3,7,8,2}, the result is 35 (i.e. 5*7, between 5 and 8).
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/oGndEKPfn.
Solution
Let's consider the outermost two boundaries.
If we switch one of the boundaries, we are decreasing the distance, so the only way to improve the area is to switch the lower of the two boundaries.
Switching the higher one decreases the distance without improving the height (because the height is dictated by the lower of the two boundaries).
Therefore, to get the maximum, we can repeatedly apply this logic, keeping track of the maximum area as we go.
