← all entries
A-029● Day 292026.06.04mediumleetcode #74neetcode150

Search a 2D Matrix

#array#binary-search#matrix
↗ leetcode #74 · search-a-2d-matrix
01

Problem

· problem
P.029

Search a 2D Matrix

↗ leetcode #74

You are given an m x n integer matrix with the following two properties: Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise. You must write a solution in O(log(m * n)) time complexity.

constraints
  • · 1 ≤ m, n ≤ 100
  • · Each row sorted in non-decreasing order
  • · First element of each row > last element of previous row
  • · -10⁴ ≤ matrix values, target ≤ 10⁴
// paraphrased summary — see source for full text
examples
example 1input → output
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
3
true
example 2input → output
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
13
false
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Can we treat the entire matrix as a single globally sorted 1D array?
  • ☐
    What does the O(log(m*n)) time requirement suggest about the solution?
  • ☐
    Why can comparing target with matrix[row][0] and matrix[row][-1] identify the correct row?
  • ☐
    Once we identify the correct row, what is the next step?
  • ☐
    Do we need to search every row to ensure correctness?
  • ☐
    Is an O(m + n) solution acceptable if it is simpler to implement?
  • ☐
    Is linear scanning each row essential to the solution?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize matrix dimensions
○
ROWS, COLS = len(matrix), len(matrix[0])
○
ROWS, COLS = len(matrix[0]), len(matrix)
○
ROWS, COLS = len(matrix), len(matrix)
step 2· Set row search bounds
○
top, bot = 0, ROWS - 1
○
top, bot = 1, ROWS - 1
○
top, bot = 0, ROWS
step 3· Compare target with row boundaries│ nested
○
if target > matrix[row][-1]:
○
if target > matrix[row][0]:
○
if target >= matrix[row][-1]:
step 4· Verify row was found
○
if not (top <= bot):
○
if top == bot:
○
if top > bot:
step 5· Binary search within row│ nested
○
if target > matrix[row][m]:
○
if target > matrix[row][l]:
○
if target >= matrix[row][m]:
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3
        ROWS, COLS = len(matrix), len(matrix[0])
4
5
        top, bot = 0, ROWS - 1
6
        while top <= bot:
7
            row = (top + bot) // 2
8
            if target > matrix[row][-1]:
9
                top = row + 1
10
            elif target < matrix[row][0]:
11
                bot = row - 1
12
            else:
13
                break
14
15
        if not (top <= bot):
16
            return False
17
        row = (top + bot) // 2
18
        l, r = 0, COLS - 1
19
        while l <= r:
20
            m = (l + r) // 2
21
            if target > matrix[row][m]:
22
                l = m + 1
23
            elif target < matrix[row][m]:
24
                r = m - 1
25
            else:
26
                return True
27
        return False
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
3
→
true
case 2
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
13
→
false
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.