Array
Binary Search
Matrix
Description
You are given an m x n
integer matrix matrix
with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target
, return true
if target
is in matrix
or false
otherwise .
You must write a solution in O(log(m * n))
time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
Solutions
Solution 1: Binary Search
We can logically unfold the two-dimensional matrix and then perform binary search.
The time complexity is $O(\log(m \times n))$, where $m$ and $n$ are the number of rows and columns of the matrix, respectively. The space complexity is $O(1)$.
Python3 Java C++ Go TypeScript Rust JavaScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool :
m , n = len ( matrix ), len ( matrix [ 0 ])
left , right = 0 , m * n - 1
while left < right :
mid = ( left + right ) >> 1
x , y = divmod ( mid , n )
if matrix [ x ][ y ] >= target :
right = mid
else :
left = mid + 1
return matrix [ left // n ][ left % n ] == target
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public boolean searchMatrix ( int [][] matrix , int target ) {
int m = matrix . length , n = matrix [ 0 ] . length ;
int left = 0 , right = m * n - 1 ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
int x = mid / n , y = mid % n ;
if ( matrix [ x ][ y ] >= target ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return matrix [ left / n ][ left % n ] == target ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public :
bool searchMatrix ( vector < vector < int >>& matrix , int target ) {
int m = matrix . size (), n = matrix [ 0 ]. size ();
int left = 0 , right = m * n - 1 ;
while ( left < right ) {
int mid = left + right >> 1 ;
int x = mid / n , y = mid % n ;
if ( matrix [ x ][ y ] >= target ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
return matrix [ left / n ][ left % n ] == target ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 func searchMatrix ( matrix [][] int , target int ) bool {
m , n := len ( matrix ), len ( matrix [ 0 ])
left , right := 0 , m * n - 1
for left < right {
mid := ( left + right ) >> 1
x , y := mid / n , mid % n
if matrix [ x ][ y ] >= target {
right = mid
} else {
left = mid + 1
}
}
return matrix [ left / n ][ left % n ] == target
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 function searchMatrix ( matrix : number [][], target : number ) : boolean {
const m = matrix . length ;
const n = matrix [ 0 ]. length ;
let left = 0 ;
let right = m * n ;
while ( left < right ) {
const mid = ( left + right ) >>> 1 ;
const i = Math . floor ( mid / n );
const j = mid % n ;
if ( matrix [ i ][ j ] === target ) {
return true ;
}
if ( matrix [ i ][ j ] < target ) {
left = mid + 1 ;
} else {
right = mid ;
}
}
return false ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 use std :: cmp :: Ordering ;
impl Solution {
pub fn search_matrix ( matrix : Vec < Vec < i32 >> , target : i32 ) -> bool {
let m = matrix . len ();
let n = matrix [ 0 ]. len ();
let mut i = 0 ;
let mut j = n ;
while i < m && j > 0 {
match matrix [ i ][ j - 1 ]. cmp ( & target ) {
Ordering :: Equal => {
return true ;
}
Ordering :: Less => {
i += 1 ;
}
Ordering :: Greater => {
j -= 1 ;
}
}
}
false
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function ( matrix , target ) {
const m = matrix . length ,
n = matrix [ 0 ]. length ;
let left = 0 ,
right = m * n - 1 ;
while ( left < right ) {
const mid = ( left + right + 1 ) >> 1 ;
const x = Math . floor ( mid / n );
const y = mid % n ;
if ( matrix [ x ][ y ] <= target ) {
left = mid ;
} else {
right = mid - 1 ;
}
}
return matrix [ Math . floor ( left / n )][ left % n ] == target ;
};
Solution 2: Search from the Bottom Left or Top Right
Here, we start searching from the bottom left corner and move towards the top right direction. We compare the current element $matrix[i][j]$ with $target$:
If $matrix[i][j] = target$, we have found the target value and return true
.
If $matrix[i][j] > target$, all elements to the right of the current position in this row are greater than target, so we should move the pointer $i$ upwards, i.e., $i = i - 1$.
If $matrix[i][j] < target$, all elements above the current position in this column are less than target, so we should move the pointer $j$ to the right, i.e., $j = j + 1$.
If we still can't find $target$ after the search, return false
.
The time complexity is $O(m + n)$, where $m$ and $n$ are the number of rows and columns of the matrix, respectively. The space complexity is $O(1)$.
Python3 Java C++ Go Rust JavaScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool :
m , n = len ( matrix ), len ( matrix [ 0 ])
i , j = m - 1 , 0
while i >= 0 and j < n :
if matrix [ i ][ j ] == target :
return True
if matrix [ i ][ j ] > target :
i -= 1
else :
j += 1
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public boolean searchMatrix ( int [][] matrix , int target ) {
int m = matrix . length , n = matrix [ 0 ] . length ;
for ( int i = m - 1 , j = 0 ; i >= 0 && j < n ;) {
if ( matrix [ i ][ j ] == target ) {
return true ;
}
if ( matrix [ i ][ j ] > target ) {
-- i ;
} else {
++ j ;
}
}
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
bool searchMatrix ( vector < vector < int >>& matrix , int target ) {
int m = matrix . size (), n = matrix [ 0 ]. size ();
for ( int i = m - 1 , j = 0 ; i >= 0 && j < n ;) {
if ( matrix [ i ][ j ] == target ) return true ;
if ( matrix [ i ][ j ] > target )
-- i ;
else
++ j ;
}
return false ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 func searchMatrix ( matrix [][] int , target int ) bool {
m , n := len ( matrix ), len ( matrix [ 0 ])
for i , j := m - 1 , 0 ; i >= 0 && j < n ; {
if matrix [ i ][ j ] == target {
return true
}
if matrix [ i ][ j ] > target {
i --
} else {
j ++
}
}
return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 use std :: cmp :: Ordering ;
impl Solution {
pub fn search_matrix ( matrix : Vec < Vec < i32 >> , target : i32 ) -> bool {
let m = matrix . len ();
let n = matrix [ 0 ]. len ();
let mut left = 0 ;
let mut right = m * n ;
while left < right {
let mid = left + ( right - left ) / 2 ;
let i = mid / n ;
let j = mid % n ;
match matrix [ i ][ j ]. cmp ( & target ) {
Ordering :: Equal => {
return true ;
}
Ordering :: Less => {
left = mid + 1 ;
}
Ordering :: Greater => {
right = mid ;
}
}
}
false
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 /**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function ( matrix , target ) {
const m = matrix . length ,
n = matrix [ 0 ]. length ;
for ( let i = m - 1 , j = 0 ; i >= 0 && j < n ; ) {
if ( matrix [ i ][ j ] == target ) {
return true ;
}
if ( matrix [ i ][ j ] > target ) {
-- i ;
} else {
++ j ;
}
}
return false ;
};
GitHub