240_Search a 2D Matrix II
[Medium]
Write an efficient algorithm that searches for a value in an mxn 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:
Consider the following matrix:
Given target = 5
, return true
.
Given target = 20
, return false
.
Solution:
Idea:
Start from top-right, check if the element equals to target.
If equal, return True.
If larger than target, move to the left.
If smaller than target, move to below.
Time Complexity: where m is the number of row, n is the number of column.
Space Complexity:
Last updated