2 minutes
Leetcode 598
The idea of this solution is pretty simple, the positions with the max value will be in the sub-matrix of range 0 to minimum y pos
, and 0 to minimum x pos
.
If you don’t understand look at the example bellow:
input: m = 6, n = 5, ops = [[4, 3], [2, 6], [3, 5]]
(Note: They give the input 1-indexed
, instead of 0-indexed
)
As you can see, all rectangles top left corner is (0, 0)
(I added an orange dot at (0, 0)
). And the sub-matrix that has the maximum values is surrounded by the yellow dotted line.
We have four parts of the dotted line, the top
, bottom
, right
, and left
.
- The
top
line is on thex-axis
, so we don’t have to worry about that. - The
left
line is on they-axis
, so we also don’t have to worry about that. - The
right
line is the minimumx
value in all theops
because the minimum is the max position that we know we have all the operations in. - The
bottom
line is the minimumy
value inops
, and it is that for the same reason as theright
line.
Read other posts