HNHacker News
TopNewBestAskShowJobs

leetthrowaway

5 karma · joined April 6, 2022

submissionscomments
leetthrowaway··on Ask HN: How are you supposed to use LeetCode?
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!

leetthrowaway··on Ask HN: How are you supposed to use LeetCode?
> I regularly see similar problems at work.

No way anyone gets that in 30 minutes without having seen it exactly before. Moving pointers in from the sides, according to Y height, both at the same time when equal, and then not using that to find the solution, just to narrow the search space? I mean, it's not like I and everyone else didn't think along those lines, but that exact algorithm is totally non-obvious. I spent like 20 minutes on something similar, another 20 on a recursive split/merge thing that went nowhere, then got brute force working.