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 in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

## Analysis

### Brute-Force

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

Iterate over elements along the diagonal, and each time perform binary search horizontally and vertically.

Note:

Time: $O(N\log{M})$ or $O(M\log{N})$
Space: $O(1)$

### Search Space Reduction

Start from the corner up-right or bottom-left.

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

### Divide and Conquer

Marked. I don’t quite really understand.

Time: $O(N\log{N})$
Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.