6-12 lines, O(log(m) + log(n)), myself+library

  • 5

    I have two solutions, one without and one with using the library. Both have runtime O(log(m) + log(n)), or in other words, O(log(mn)).

    Solution 1: One Binary Search (48 ms, 12 lines)

    Here I treat the matrix like a single big list of length m*n and use a simple binary search. I only have to convert the list indexes to matrix indexes on the fly.

    def searchMatrix(self, matrix, target):
        n = len(matrix[0])
        lo, hi = 0, len(matrix) * n
        while lo < hi:
            mid = (lo + hi) / 2
            x = matrix[mid/n][mid%n]
            if x < target:
                lo = mid + 1
            elif x > target:
                hi = mid
                return True
        return False

    Solution 2: Using the library (48 ms, 6 lines)

    If there were a library function doing the 2D search, it would be boring, but there isn't. So it's still a little challenge to figure out how to use the 1D functions that are there. Here I use bisect to (approximately) find the candidate row and then bisect_left to find the candidate cell in that row.

    def searchMatrix(self, matrix, target):
        i = bisect.bisect(matrix, [target])
        if i < len(matrix) and matrix[i][0] == target:
            return True
        row = matrix[i-1]
        j = bisect.bisect_left(row, target)
        return j < len(row) and row[j] == target

  • 1

    Why do we have to set hi = mid instead of hi = mid - 1 in your first solution? Thx.

  • 0

    @dianhua1560 My hi is exclusive, so setting it to mid - 1 would rule that out. But it shouldn't.

  • 0

    got it. Thanks!

  • 0

    Great job!!!

  • 1

    Here is my 1-line python, hope that you like it:

    def searchMatrix(self, matrix, target):
            return bool(matrix) and target in matrix[bisect.bisect(matrix, [target + 0.5]) - 1]

    If you want to do bisect twice:

    def searchMatrix(self, matrix, target):
            m = bisect.bisect(matrix, [target+0.5])
            return len(matrix[0]) > 0 and matrix[m - 1][bisect.bisect(matrix[m - 1], target) - 1] == target if m else False

    which equals to:

    def searchMatrix(self, matrix, target):
            m = bisect.bisect(matrix, [target + 0.5])
            if m:
                n = bisect.bisect(matrix[m - 1], target)
                return len(matrix[0]) > 0 and matrix[m - 1][n - 1] == target
            return False

  • 0

    @lee215 I like the one-liner, though it has different complexity. In your other solutions I don't like the redefinition of m and n. The problem already defined them to be height and width of the matrix (as is the standard in math/compsci).

    Slight variation:

    def searchMatrix(self, matrix, target):
        i = bisect.bisect(matrix, [target + 0.5]) - 1
        return any(matrix) and matrix[i][bisect.bisect(matrix[i], target) - 1] == target

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.