Search a 2D Matrix II

medium array binary search matrix

Problem

Search for a value in an m×n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom. Return true if found.

Inputmatrix shown below, target = 5

Outputtrue

Walk from the top-right: if cell > target step left, else step down. O(m + n).

matrix (rows separated by ; cells by ,)

target

def search_matrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    r, c = 0, n - 1
    while r < m and c >= 0:
        v = matrix[r][c]
        if v == target: return True
        if v > target: c -= 1
        else: r += 1
    return False

function searchMatrix(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let r = 0, c = n - 1;
  while (r < m && c >= 0) {
    const v = matrix[r][c];
    if (v === target) return true;
    if (v > target) c--;
    else r++;
  }
  return false;
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int r = 0, c = n - 1;
        while (r < m && c >= 0) {
            int v = matrix[r][c];
            if (v == target) return true;
            if (v > target) c--;
            else r++;
        }
        return false;
    }
}

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int r = 0, c = n - 1;
    while (r < m && c >= 0) {
        int v = matrix[r][c];
        if (v == target) return true;
        if (v > target) c--;
        else r++;
    }
    return false;
}

Explanation

This matrix is sorted along both rows and columns, but not as one flat sorted list, so plain binary search does not apply. The neat trick is to start at the top-right corner and walk inward.

Why the top-right? That cell is the largest in its row and the smallest in its column. That special position means a single comparison tells us exactly which direction to move, eliminating a whole row or column each step.

At each cell matrix[r][c]: if it equals the target we are done. If it is greater than the target, everything below in this column is even bigger, so we step left with c--. If it is smaller, everything to the left in this row is even smaller, so we step down with r++.

Example: searching for 5, start at the top-right 15. 15 > 5 so step left to 11, then 7 — both too big, keep stepping left to 4. Now 4 < 5 so step down, landing on 5. Found.

Each step removes one row or one column, so we make at most m + n moves — far better than scanning the whole grid.

Time: O(m + n) Space: O(1)