# Using Python to search a sorted 2D Matrix

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.

• O(n) > O(log(n)) – alexyorke Dec 4 '19 at 1:59
• @alexyorke but O(n + k) < O(n log k) for the most part. – Quintec Dec 4 '19 at 2:49
• @Quintec ah, that is correct – alexyorke Dec 4 '19 at 3:12
• 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) – Sriv Dec 4 '19 at 7:31

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\$$, $$\2n > n\log_b n\$$ for $$\n < b^2\$$).