By Long Luo

This article is the solution 5 Approaches: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis of Problem 240. Search a 2D Matrix II.

Here shows 5 Approaches to slove this problem: Brute Force, Binary Search(Row), Binary Search(Diagonal, Row, Col), Binary Search(Global), 2D Coord Axis.

# Intuition

This problem is like 74. Search a 2D Matrix, we can refer to the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis.

# Brute Force

Just scan the $\textit{matrix}$ to find the answer.

## Analysis

• Time Complexity: $O(mn)$.
• Space Complexity: $O(1)$.

# Binary Search(Row)

Use Binary Search method in each Row to find the answer.

## Analysis

• Time Complexity: $O(min(M,N)(logM+logN))$.
• Space Complexity: $O(1)$.

# Binary Search(Diagonal, Row, Col)

This method is more difficult, we have to Binary Search method in each Diagonal, then each Row and each Column to find the answer.

## Analysis

• Time Complexity: $O(min(M,N)(logM+logN))$.
• Space Complexity: $O(1)$.

# Binary Search(Global)

Consider the $\textit{matrix}$ as a $1-D$ array, and the Binary Search the array.

## Analysis

• Time Complexity: $O(mlogn)$.
• Space Complexity: $O(1)$.

# 2D Coord Axis

The $2D$ array increases from left to right and from top to bottom.

1. Each column, all the numbers above are all smaller than it.
2. Each row, the right of the number are all larger than it.

Therefore, the algorithm is as follows:

1. From the bottom left corner of the $2D$ array as the origin, take it as a $2D$ coordinate axis;
2. If the current number is larger than the $\textit{target}$, moves up;
3. If the current number is less than the $\textit{target}$, move right.

## Analysis

• Time Complexity: $O(m + n)$.
• Space Complexity: $O(1)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗