Search a 2D Matrix

easyPROSorting & SearchingNetflix DSA

Given an m x n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row, determine if a target value exists.

Implement search_matrix(matrix, target), where matrix is a list of rows (each a list of integers) and target is an integer. Return True if target appears in the matrix, otherwise False.

Example

Input

1,3,5,7
10,11,16,20
23,30,34,60
3

Output

True

Reasoning

Input: matrix is a $3 \times 4$ grid of integers and target is 3. Each row increases left to right, and every row starts above where the previous one ended.
Each row therefore covers its own value range: row 0 spans $[1, 7]$ , row 1 spans $[10, 20]$ , row 2 spans $[23, 60]$ , and these ranges do not overlap.
$3$ lies in row 0's range, since $1 \le 3 \le 7$ . Rows 1 and 2 start at $10$ and $23$ , both above $3$ .
Row 0 holds $1, 3, 5, 7$ , and its second entry (row 0, column 1) equals $3$ exactly, so the answer is True.
Output: a single boolean. Notice that a value can fall inside the overall range and still be absent: a target of $13$ lies in row 1's range $[10, 20]$ but sits between $11$ and $16$ , giving False.

Constraints

1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

Learn this in

Binary SearchDSA Study Plan

More from Netflix DSA

Merge Intervalsmedium Sort Colorsmedium Kth Largest Element in an Arraymedium Missing Numbereasy Find All Duplicates in Arraymedium

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results