📘

Search a 2D Matrix

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.

Input: matrix rows comma-separated, then target on last line.

Example:

Input:

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

Output:

True

Reasoning:

The input matrix is: 1, 3, 5, 7 10, 11, 16, 20 23, 30, 34, 60
We treat the 2D matrix as a 1D sorted array: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60
To find the target value 3, we can use a binary search algorithm, which has a time complexity of $O(\log(mn))$
Since 3 is present in the sorted array, the output is True

Constraints:

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

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.