Katkat
Back

Search for a Target in a Matrix Sorted by Rows and Columns

Goldman SachsSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests the ability to search efficiently in a 2D grid sorted along both dimensions by exploiting boundary invariants to achieve an O(m + n) time complexity.

Problem Statement

You are given an m x n integer matrix matrix and an integer target. The matrix has the following properties:

  • Integers in each row are sorted in non-decreasing order from left to right.
  • Integers in each column are sorted in non-decreasing order from top to bottom.

Write a function that returns True if target exists in the matrix, and False otherwise.

Function Signature

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    pass

Input & Output Format

  • Input:
    • matrix: A 2D list of integers of dimensions m x n.
    • target: An integer to locate.
  • Output: A boolean (True or False).

Constraints

  • m == len(matrix)
  • n == len(matrix[0])
  • 1 <= m, n <= 1000
  • -10^9 <= matrix[i][j] <= 10^9
  • -10^9 <= target <= 10^9

Examples

Example 1

Input: matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
], target = 5
Output: True
Explanation: 5 is located at matrix[1][1].

Example 2

Input: matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
], target = 20
Output: False
Explanation: 20 is not present anywhere in the matrix.

Edge Cases to Consider

  • Matrices with a single row or single column (1 x n or m x 1).
  • Targets strictly smaller than matrix[0][0] or strictly larger than matrix[m - 1][n - 1].
  • Matrices containing repeated/duplicate elements.

Hints

Hint 1

Notice that starting at the top-left or bottom-right corner does not provide a clear direction to move because both adjacent paths increase or decrease simultaneously.

Hint 2

Consider starting at the top-right or bottom-left corner where moving along one axis increases the value while moving along the other decreases it.

Hint 3

From the top-right corner, if the current element is greater than the target, move left; if it is less, move down.

Follow-up questions

  • Can you extend your approach to count the total number of times the target appears when duplicates exist?
  • How does a divide-and-conquer / quad-tree search compare to the O(m + n) corner-walk approach when m is substantially larger than n?
  • If the matrix is stored on disk row-by-row and page faults are expensive, would you still traverse step-by-step or change the search strategy?