Two Pointers
Proving a discard is safe
When the two ends are not symmetric, one side is provably useless. Finding which one is the whole problem.
A different kind of decision
In the sorted-sum search, the comparison told you which pointer to move because the sum moved predictably. Some problems have no target to compare against. Instead the quantity you care about depends on both ends at once, and you have to reason about which end is holding you back.
Here is a toy version. Two vertical posts of given heights stand at given positions. The rectangle they enclose has width equal to the distance between them and height equal to the shorter post, since anything taller spills over. Find the largest such rectangle.
Why it works
The question to ask
Start with the pointers at the two ends, which is the widest the rectangle can ever be. Any move inward loses width. So a move is only worth making if it can gain more in height than it loses in width, and you cannot know that in advance.
Turn the question around. Instead of asking which move is best, ask which move is safe. Which of the two current posts can be discarded without any risk of losing the answer?
Key idea
The shorter post is the one to discard
Take the shorter of the two posts. Every rectangle that still uses it must pair it with some post between the two pointers, which is strictly narrower than the current pairing. Its height is still capped by the shorter post or by something even shorter.
So every remaining rectangle using the shorter post is no wider and no taller than the one you just measured. None of them can beat it. Discarding the shorter post loses nothing, and it is the only side you can say that about: the taller post might pair with something even taller later.
That argument turns the quadratic scan into a single walk inward. Here is what it looks like at the very first step, on the same posts.
Why it works
What the loop looks like
Repeat those two lines. Measure the current pairing, then step the limiting side inward. The loop ends when the pointers meet, because a pairing needs two distinct posts.
Each pass throws away exactly one post and never revisits it, so the walk is O(n) with O(1) extra space. Note that the running best has to be updated before the discard, since the pairing you are about to break up may be the answer.
Edge cases
When the two sides are equal
If the heights are equal, either side can move and the answer is unaffected. Both remaining candidates on that side are capped by the same height and are narrower, so neither can win.
Moving both at once is also correct here, and moving neither is an infinite loop. Whenever a comparison has a tie case, decide explicitly what happens rather than letting an else catch it by accident.
Tip
The general form of the argument
This shape recurs. You hold two candidates, you can only keep one, and you want to discard the one that provably cannot appear in any better answer. The proof always has the same skeleton: show that every future pairing involving this candidate is dominated by the pairing you just measured.
When you can make that argument, the loop is O(n). When you cannot, you are guessing, and a greedy discard that is not justified is the most common way an interview solution is subtly wrong while passing the examples in the prompt.
One more, and it is harder
The next problem uses a discard argument too, and the quantity being tracked is less obvious. Before you write anything, work out what each position contributes to the answer, and what you would need to know about both sides in order to compute that contribution.
Which side moves?
Pointers sit at heights 8 on the left and 3 on the right. Which move is provably safe, and why?
Container With Most Water
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.