Using Python to search a sorted 2D Matrix

Question

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.

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
– Sriv, Commented Dec 4, 2019 at 7:31

Graipher · Accepted Answer · 2019-12-04 13:39:42Z

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\$).

Stack Exchange Network

Using Python to search a sorted 2D Matrix

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Using Python to search a sorted 2D Matrix

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions