Search in a Row and Column-Wise Sorted Matrix

Given an M x N integer matrix matrix and an integer target, return true if target exists in the matrix, otherwise return false.

In this matrix:

• Each row is sorted from left to right.

• Each column is sorted from top to bottom.

Brute Force Approach

The simplest thought is to just check every value one by one.

If any cell matches the target, the search can stop immediately.

This approach is useful as a starting point because it matches exactly what the problem is asking, even though it does not use the matrix properties in a smart way.

Algorithm

• First, check whether the matrix is empty. This is needed so the code does not try to access a row or column that does not exist.

• Traverse every row because the target can be in any part of the matrix.

• Inside each row, traverse every column and compare the current value with the target.

• If the current value matches the target, return true immediately because the answer has been found.

• If the full matrix is checked and no match appears, return false because the target is not present.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(M x N), M is the number of rows and N is the number of columns, because in the worst case every cell of the matrix may need to be checked.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The unlocking observation comes from choosing the right starting corner. The top-right element is a very special position.

• Everything on its left is smaller.

• Everything below it is larger.

That means one comparison is enough to decide one whole direction. If the current value is larger than the target, moving down makes things even larger, so that cannot help. The only useful move is left.

If the current value is smaller than the target, moving left makes things even smaller, so that cannot help either. The only useful move is down.

This is the full reason the method works. Each step removes one row or one column from consideration, so the search keeps shrinking in a very controlled way.

This pattern often feels like walking down a staircase, which is why this method is commonly called staircase search.

Algorithm

• First, check whether the matrix is empty. This is needed so the search does not try to read an invalid corner position.

• Start from the top-right cell using row = 0 and col = cols - 1. This corner is chosen because it gives opposite directions: left becomes smaller and down becomes larger.

• Compare the current value with the target. If both values are equal, return true immediately because the target has been found.

• If the current value is greater than the target, move left by decreasing col. This is done because the full current column below this cell is even larger, so that column cannot contain the target at this position or below.

• If the current value is smaller than the target, move down by increasing row. This is done because the full current row to the left is even smaller, so staying in that row cannot help anymore.

• Keep repeating this process while row stays inside the matrix and col stays inside the matrix.

• If the search goes out of bounds, return false because every useful row or column has already been ruled out.

Key Points

• This problem is not globally sorted like Search in a 2D Matrix, so flattening into a virtual 1D array does not work here. Check the article on Search in a 2D Matrix

• Starting from the bottom-left corner also works for the same reason, just with opposite moves.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(M + N),M is the number of rows and N is the number of columns,because in each step one row or one column is removed from the search.

Space Complexity: O(1), because constant space is used.