Each row is sorted left to right, and each column is sorted top to bottom. Return true if the target is in the matrix.
DSA Animator › DSA Revision › Matrix › Search a 2D Matrix II
Remember: start at a corner where one move goes up in value and the other goes down. Top right: too big, go left. Too small, go down. The video solves Search a 2D Matrix II (LeetCode 240, Medium) with the Staircase Search pattern from the Matrix topic, and you can replay every step in the interactive Search a 2D Matrix II animation.
Each row is sorted left to right, and each column is sorted top to bottom. Return true if the target is in the matrix.
In this 5 by 5 matrix, the target 5 is present, at row 1, column 1.
Checking every cell is O of m times n. Binary searching each row is better, but still O of m log n.
Start at the top right corner. Everything to its left is smaller, and everything below it is bigger. So if the value is too big, move left, and if it is too small, move down. Each step removes a whole row or a whole column.
Start at 15, which is bigger than 5, so move left. 11 is still bigger, so move left. 7 is bigger, so move left again. 4 is smaller than 5, so move down. Now we land on 5, which is the target.
In code, start at row 0 and the last column. While inside the matrix, compare the value with the target. Return true on a match, move left when it is bigger, and move down when it is smaller. At most m plus n steps, so it's O of m plus n time and O of 1 space.
Remember: start at a corner where one move goes up in value and the other goes down. Top right: too big, go left. Too small, go down.