Search In Sorted Matrix

Tags

Search In Sorted Matrix

Category

Searching

Difficulty

Medium

Problem Statement

Given a two-dimensional matrix where each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom, determine whether a target value exists in the matrix. Return the row and column indices if found, or [-1, -1] otherwise.

Intuition

Starting from the top-right corner (or bottom-left corner) gives a unique vantage point. If the current element is larger than the target, we can eliminate the entire current column by moving left. If it is smaller, we can eliminate the entire current row by moving down. Each step eliminates a full row or column.

Approach

  1. Start at the top-right corner: row = 0, col = number of columns - 1.
  2. While row is within bounds and col >= 0:
    • If matrix[row][col] == target, return [row, col].
    • If matrix[row][col] > target, move left (col -= 1). The target cannot be in this column since all values below are even larger.
    • If matrix[row][col] < target, move down (row += 1). The target cannot be in this row since all values to the left are even smaller.
  3. If the loop exits, the target is not in the matrix — return [-1, -1].

Pseudocode

function searchInSortedMatrix(matrix, target):
    row = 0
    col = length(matrix[0]) - 1
    while row < length(matrix) and col >= 0:
        if matrix[row][col] == target:
            return [row, col]
        else if matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return [-1, -1]

Time & Space Complexity

  • Time: O(n + m) — where n is the number of rows and m is the number of columns. At each step, either row increases or column decreases, so at most n + m steps occur.
  • Space: O(1) — Only two index variables are used.

Key Insights

  • The top-right and bottom-left corners are the only starting positions where each comparison eliminates a full row or column. Starting from the top-left or bottom-right does not have this property.
  • This is more efficient than binary-searching each row (O(n log m)) for matrices where n and m are comparable in size.
  • The algorithm works regardless of whether the matrix has equal rows and columns (works on rectangular matrices).

Edge Cases

  • Single-element matrix — one comparison determines the result.
  • Target is smaller than the top-left element — eliminated immediately by moving left from the top-right.
  • Target is larger than the bottom-right element — eliminated by moving down past the last row.
  • Target appears multiple times — the algorithm finds one occurrence (not necessarily a specific one).
  • Matrix with one row or one column — degenerates to a linear search, still O(n + m).

Linked mentions