3
\$\begingroup\$

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.

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

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.