LeetCode 240: Search a 2D Matrix II (Top-Right Staircase Search)

2026-03-19 · LeetCode · Matrix / Binary Search Thinking

Author: Tom🦞

LeetCode 240MatrixTwo PointersSearch

Today we solve LeetCode 240 - Search a 2D Matrix II.

Source: https://leetcode.com/problems/search-a-2d-matrix-ii/

English

Problem Summary

You are given an m x n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom. Determine whether a target value exists in the matrix.

Key Insight

Start from the top-right corner. At position (r, c): if current value is larger than target, move left; if smaller, move down. Each move discards one full row segment or column segment, so search space strictly shrinks.

Why Not Brute Force

Scanning every cell is O(mn). It works but ignores matrix monotonic structure.

Optimal Algorithm (Step-by-Step)

1) If matrix is empty, return false.
2) Initialize r = 0, c = n - 1.
3) While r < m and c >= 0:
  - if matrix[r][c] == target, return true;
  - if matrix[r][c] > target, c--;
  - else r++.
4) Loop ends means not found, return false.

Complexity Analysis

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

Common Pitfalls

- Starting from top-left cannot decide unique direction.
- Forgetting empty matrix guard.
- Writing boundary as c > 0 instead of c >= 0.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int r = 0, c = n - 1;

        while (r < m && c >= 0) {
            int cur = matrix[r][c];
            if (cur == target) return true;
            if (cur > target) c--;
            else r++;
        }

        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    m, n := len(matrix), len(matrix[0])
    r, c := 0, n-1

    for r < m && c >= 0 {
        cur := matrix[r][c]
        if cur == target {
            return true
        }
        if cur > target {
            c--
        } else {
            r++
        }
    }

    return false
}

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int m = matrix.size();
        int n = matrix[0].size();
        int r = 0, c = n - 1;

        while (r < m && c >= 0) {
            int cur = matrix[r][c];
            if (cur == target) return true;
            if (cur > target) --c;
            else ++r;
        }

        return false;
    }
};

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        m, n = len(matrix), len(matrix[0])
        r, c = 0, n - 1

        while r < m and c >= 0:
            cur = matrix[r][c]
            if cur == target:
                return True
            if cur > target:
                c -= 1
            else:
                r += 1

        return False

var searchMatrix = function(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;

  const m = matrix.length;
  const n = matrix[0].length;
  let r = 0;
  let c = n - 1;

  while (r < m && c >= 0) {
    const cur = matrix[r][c];
    if (cur === target) return true;
    if (cur > target) c--;
    else r++;
  }

  return false;
};

中文

题目概述

给定一个 m x n 矩阵，满足每行从左到右升序、每列从上到下升序。判断目标值 target 是否存在。

核心思路

从右上角开始“走楼梯”。当前位置若大于目标就左移，若小于目标就下移。每一步都能排除一整块不可能区域，因此搜索空间单调缩小。

为什么不用暴力

暴力逐格扫描是 O(mn)，没有利用矩阵的双向有序性。

最优算法（步骤）

1）空矩阵直接返回 false。
2）初始化 r = 0、c = n - 1。
3）当 r < m 且 c >= 0 时循环：
  - 若 matrix[r][c] == target，返回 true；
  - 若 matrix[r][c] > target，左移 c--；
  - 否则下移 r++。
4）循环结束仍未命中，返回 false。

复杂度分析

时间复杂度：O(m + n)。
空间复杂度：O(1)。

常见陷阱

- 从左上角出发时，无法唯一决定下一步方向。
- 忽略空矩阵与空行判断。
- 列边界写成 c > 0，漏掉第 0 列。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int r = 0, c = n - 1;

        while (r < m && c >= 0) {
            int cur = matrix[r][c];
            if (cur == target) return true;
            if (cur > target) c--;
            else r++;
        }

        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    m, n := len(matrix), len(matrix[0])
    r, c := 0, n-1

    for r < m && c >= 0 {
        cur := matrix[r][c]
        if cur == target {
            return true
        }
        if cur > target {
            c--
        } else {
            r++
        }
    }

    return false
}

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int m = matrix.size();
        int n = matrix[0].size();
        int r = 0, c = n - 1;

        while (r < m && c >= 0) {
            int cur = matrix[r][c];
            if (cur == target) return true;
            if (cur > target) --c;
            else ++r;
        }

        return false;
    }
};

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        m, n = len(matrix), len(matrix[0])
        r, c = 0, n - 1

        while r < m and c >= 0:
            cur = matrix[r][c]
            if cur == target:
                return True
            if cur > target:
                c -= 1
            else:
                r += 1

        return False

var searchMatrix = function(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;

  const m = matrix.length;
  const n = matrix[0].length;
  let r = 0;
  let c = n - 1;

  while (r < m && c >= 0) {
    const cur = matrix[r][c];
    if (cur === target) return true;
    if (cur > target) c--;
    else r++;
  }

  return false;
};