74. Search a 2D Matrix

Quick Identifier

• Topic: binary-search
• Pattern: Binary Search (Implicit 1D order)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 74

Quick Sights

• Time Complexity: O(log(m*n)) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: Given an m x n matrix with rows sorted left-to-right and each row’s first value greater than the previous row’s last, decide if target appears. Treat row-major order as one sorted array of length m*n.

Concept Explanation

Given an m x n matrix with rows sorted left-to-right and each row’s first value greater than the previous row’s last, decide if target appears. Treat row-major order as one sorted array of length m*n.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• Matrix + “sorted” + full row-major monotonicity
• “O(log(m*n))” or “binary search” hint
• Each row sorted and starts after prior row’s maximum

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(m*n) time / O(1) space — scan every cell.
• Better — O(m+n) time / O(1) space — staircase from top-right (two-pointer exploit).
• Optimal — O(log(m*n)) time / O(1) space — binary search rank mid → (mid / n, mid % n).

Optimal Solution

Go

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	rows, cols := len(matrix), len(matrix[0])
	left, right := 0, rows*cols-1
	for left <= right {
		mid := left + (right-left)/2
		row := mid / cols
		col := mid % cols
		current := matrix[row][col]
		if current == target {
			return true
		}
		if current < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}

JavaScript

function searchMatrix(matrix, target) {
	if (matrix.length === 0 || matrix[0].length === 0) {
		return false;
	}
	const rows = matrix.length;
	const cols = matrix[0].length;
	let left = 0;
	let right = rows * cols - 1;
	while (left <= right) {
		const mid = left + Math.floor((right - left) / 2);
		const row = Math.floor(mid / cols);
		const col = mid % cols;
		const current = matrix[row][col];
		if (current === target) {
			return true;
		}
		if (current < target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return false;
}

Walkthrough

Matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3, rows=3, cols=4

Virtual array: [1,3,5,7,10,11,16,20,23,30,34,60]. Search 3: compare mid values until hit index 1.

Invariant: row-major indices preserve sorted order, so standard binary search applies on rank.

Edge Cases

• Single row or single column matrix.
• Target smaller than top-left or larger than bottom-right.
• Empty matrix (per constraints, handle defensively).

Pitfalls

• Confusing with “each row sorted” only (different problem) — here global order must hold.
• Wrong col = mid % cols when using wrong cols (ragged rows — problem assumes rectangle).

Similar Problems

• 704. Binary Search — same loop on a plain array.
• 35. Search Insert Position — index-as-rank mindset (lower bound).
• 875. Koko Eating Bananas — monotonic predicate mapped to search space.

Variants

• Rows-only sorted (LeetCode 240) — staircase or binary search on row start then row.
• Strict matrix shapes — watch empty rows.

Mind-Map Tags

#binary-search #matrix #row-major #implicit-sorted-array