Comment by trinovantes | Hacker News Reader

Comment by trinovantes | Hacker News Reader

I don't think it's that non obvious. You're maximizing the area A = H*W which means maximizing H and W. Obviously the largest W is between height[0] and height[n-1]. You don't know if this will give the largest A as there might be a pair of heights with smaller W so you have to search inside. If you decrease W but want to increase A, then H must increase. From this you should recognize that the only way to increase H is with an inner line that's higher than min(height[0], height[n-1]). Any other lines cannot mathematically be candidates for a larger area. Once you know how to select your candidates, it's just a matter of checking them to find the max area.

Of course trying to make this deduction during an actual interview when one or multiple people are watching you is an entirely different problem. Hopefully leetcode will give you enough practice to recognize patterns so that you don't need to think too deeply during interviews.

I don't think you have it. Say you have an input like this:

[3,2,100,100,2,3]

So you start on the outsides working in with your method, and you will stop at the two outermost 3s, because the 2 is less area, and never make it to the inner 100s. That's why the actual algorithm is to keep moving the pointers in until they meet, in a very specific way, keeping track of the maximum the whole time. It's not about actually finding the maximum and stopping early, it's about reducing the search space to O(n) from the naive O(n^2).

EDIT: However! There is a condition where h[n] <= len(h), which actually makes your method work! But you never mentioned that, so I think you may have gotten it by accident. :D

Like, with that condition, it becomes something like this:

[1,1,6,6,1,1]

and then stopping at the outer 1s is equivalent to making it in to the 6s.

I guess my issue is that I didn't example the conditions well enough. There's was a huge clue in there!

Without any conditions on the input, you cannot stop early and must visit each element at least once. The candidate selection I mentioned is for picking which edge to keep as you reduce the search space for a potentially bigger area (sorry if I didn't explain it clearly).

[3,2,100,100,2,3]

[2,100,100,2,3] (keep right 3, check if 2-3 has a larger area)

[100,100,2,3] (keep right 3, check if 100-3 has a larger area)

[100,100,2] (keep left 100, check if 100-2 has a larger area)

[100,100] (keep left 100, check if 100-100 has a larger area)

Reply on news.ycombinator.com