By Long Luo

Here are 6 approaches to solve this problem in Java.

# BF(2 Loops)

It’s easy to use 2 loops to traverse the entire matrix to find the target.

Notice that the first integer of each row is greater than the last integer of the previous row.

We can optimize the code before.

## Analysis

• Time Complexity: $O(m \times n)$
• Space Complexity: $O(1)$

# Find Row First, then Column Binary Search

We can scanning the rows of the matrix, If the target is larger than the last element of this row, the target must not be in this row, but only in the lower row of the matrix.

If we find the row which the target may appears, search this row.

## Analysis

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

# 2 Binary Search: Row and Column

Using the binary search on the elements of the first column of the matrix, find the last element that is not larger than the target, the target may be located in the row.

Search the row where the target was located.

## Analysis

• Time Complexity: $O(logm + logn)$
• Space Complexity: $O(1)$

# 1 Binary Search

Merge the current row to the end of the previous row, we can get an ascending array, then we just use binary search algorithm to find the target.

## Analysis

• Time Complexity: $O(log{mn})$
• Space Complexity: $O(1)$

# 2D Coordinate 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 target, moves up.
3. If the current number is less than the target, move right.

## Analysis

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

# Reshape

It’s easy to reshape to one-dimensional array in python, then search as a one-dimensional array.

## Analysis

• Time Complexity: $O(mn+log{mn})$
• Space Complexity: $O(mn)$

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. 😉😃💗