# 74. Search a 2D Matrix

Reference: LeetCode EPI 11.6
Difficulty: Medium

## Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example:

## Analysis

### Brute-Force

Time: $O(MN)$
Space: $O(1)$

### Starting From Corner

Note:

Time: $O(M + N)$
Space: $O(1)$

Learn the conversion between matrix indices and its corresponding list’s index.

Standard Version:

Lower Bound Version:

Remember to check boundary before returning.

Time: $O(\log{MN}) = O(\log{M} + \log{N})$
Space: $O(1)$

Comment
Junhao Wang
a software engineering cat