# Yet another way to see what happens in the O(n) algorithm

• The O(n) solution with proof by contradiction doesn't look intuitive enough to me. Before moving on, read the algorithm first if you don't know it yet.

Here's another way to see what happens in a matrix representation:

Draw a matrix where the row is the first line, and the column is the second line. For example, say `n=6`.

In the figures below, `x` means we don't need to compute the volume for that case: (1) On the diagonal, the two lines are overlapped; (2) The lower left triangle area of the matrix is symmetric to the upper right area.

We start by computing the volume at `(1,6)`, denoted by `o`. Now if the left line is shorter than the right line, then all the elements left to `(1,6)` on the first row have smaller volume, so we don't need to compute those cases (crossed by `---`).

``````  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x
4 x x x x
5 x x x x x
6 x x x x x x
``````

Next we move the left line and compute `(2,6)`. Now if the right line is shorter, all cases below `(2,6)` are eliminated.

``````  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x
``````

And no matter how this `o` path goes, we end up only need to find the max value on this path, which contains `n-1` cases.

``````  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x
``````

Hope this helps. I feel more comfortable seeing things this way.

• Your explanation is very clear and beautiful~

• thx for explain!

• Convincing and elegant explanation.

• excellent explanation

• This post is deleted!

• This post is deleted!

• I came up with this proof too, inspired by the step-wise linear search method in this blog: http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html. Glad that someone has shared the same idea.

• Really clever explanations. The illustration makes sense :-)

• Can't understand the representation.

• What do you mean by 1,2,3,4,5,6?

• great explanation!

• This kind of explanation is what I want!

• Very clear explanation, thanks!

• Very interesting, thank you!

• so great!!!thank you!

• Genius algorithm & genius explanation. Thank you.

• This post is deleted!

• how abort if the left and the down are the same ??? I try to compute the left by maxArea(height[j:i]) which i is the horizontal index and j is the vertical index, and also the down is maxArea(height[j+1:i+1]), but I get Limit Time Execute !!! I knw the reason is I compute some area again and again, but I do not know what to do ?

• amazing! genius and elegant!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.