Using Python to search a sorted 2D Matrix

Question

Code

Problem

class Solution:
 def searchMatrix(self, matrix, target):
 """
 :type matrix: List[List[int]]
 :type target: int
 :rtype: bool
 """
 if len(matrix) == 0 or len(matrix[0]) == 0:
 return False
 height = len(matrix)
 width = len(matrix[0])
 row = height - 1 
 col = 0
 while col < width and row >= 0:
 if matrix[row][col] > target:
 row -= 1
 elif matrix[row][col] < target:
 col += 1
 else:
 return True
 return False

Any improvements you could make to this? Runtime is O(Len(row) + len(col)), space is constant.

I looked at other solutions and a lot of them used binary search, but that is O(len(col) * log(len(row)) so I don't think that's an improvement.

• alexyorke: O(n) > O(log(n))
• Quintec: @alexyorke but O(n + k) < O(n log k) for the most part.
• alexyorke: @Quintec ah, that is correct
• Sriv: You could use a binary search for both the rows and columns. I guess it would be O(log(n) + log(m)) or log(n + m)

Answer 1

Unfortunately, using binary search both for rows and columns is not possible here. It fails if the last element of the first row is too small, i.e. for this input:

matrix = [[ 0, 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, 27, 28, 29]]
target = 10

However, you could use binary search within each row for \$\mathcal{O}(n\log m)\$ runtime, compared to your \$\mathcal{O}(n + m)\$ runtime, as you noted in the question. While this is nominally worse, for the actual testcases being tested by Leetcode it performs better.

from bisect import bisect_left
class Solution:
 def searchMatrix(self, matrix, target):
 """
 :type matrix: List[List[int]]
 :type target: int
 :rtype: bool
 """
 if not matrix or not matrix[0]:
 return False
 for row in matrix:
 i = bisect_left(row, target)
 if i < len(row) and row[i] == target:
 return True
 return False

Your code: 36ms, faster than 85.35%

Binary search: 28 ms, faster than 98.39%

This is probably due to the testcases being small enough (and if \$m = n\$, \2ドルn > n\log_b n\$ for \$n < b^2\$).