Calculate optimality of based on optimal substructure and overlapping subproblems

[sanjarcode]

Consider this problem to understand Trapping Water - LeetCode

Understanding the problem

Suppose we start from the left and continue, we would stop at a height >= where we started, 
and then calculate the water = left * (k - j - 1) - sum(blocks in the way).

Now, apply the same logic to the largest and 2nd largest heights. Basically, we cut the maximum height to be 
the 2nd maximum height for each case (of selection of region). 
We will basically after finding water between them, 
the part on the left and right are completely independent. 
So we do have optimal substructure. 
But we don't have overlapping subproblems. So this can be done by divide and conquer.

trap(i, j) = trap(i, a) + water(a...b) + trap(b, j) where a, b are first and second maximas (in any order). 
Trap will return a number.

Also, we can reuse the walls of a region for outer regions.
*/

/*
Approach 1 - simple recursion is optimal? because we have no overlapping subproblems, so nothing to store. 
And recursion is a must because input selection is variable for each case.

As we are doing everything optimally, this is optimal? Is it?

By the way, this gave TLE error on LeetCode.

[sanjarcode]

This is important. Until now, I've been OK with what the interviewer was satisfied with and didn't actually prove/calculate optimality. This is bad because 'interviews' are not the goal of Data Structures or Algorithm Design for that matter.

[sanjarcode]

My quick and dirty way to 'estimate' optimality. For coding questions, I calculate the time complexity of my solution and make sure it is less than 10⁸ ops/second. But, as said, it's not about winning contests, I need to prove optimality.