To solve this problem efficiently, we take advantage of the matrix's structure—each row and each column is sorted in non-decreasing order.
Understanding the Matrix Structure
Since rows are sorted left-to-right and columns are sorted top-to-bottom, this gives us a clever way to eliminate entire rows or columns at each step. We don’t need to check every cell.
Where to Start?
We begin our search at the top-right corner of the matrix. Why? Because:
- The element at the top-right is the largest in its row and the smallest in its column.
- This allows us to move left if the current element is too large or down if the current element is too small.
Step-by-Step Explanation
We set our starting position to row = 0
and col = number_of_columns - 1
. Then we enter a loop that continues until either:
- We find the target (return true), or
- We move out of bounds (return false)
At each step:
- If the current element equals the target, we’re done!
- If the current element is greater than the target, we move left (since all elements to the left are smaller).
- If the current element is less than the target, we move down (since all elements below are larger).
Handling Edge Cases
- Empty Matrix: If the matrix has no rows or columns, we return false immediately.
- Single Element Matrix: If it matches the target, return true. Otherwise, false.
- Target smaller than all elements: We’ll keep moving left until we exit the matrix.
- Target greater than all elements: We’ll keep moving down until we exit the matrix.
Why This Works
This approach ensures we only visit at most rows + columns
elements in the worst case. So even if the matrix is large, this method stays efficient. The time complexity is O(N + M), where N = number of rows and M = number of columns.