Python solution with detailed explanation


  • 1
    G

    Solution

    Search a 2D Matrix II https://leetcode.com/problems/search-a-2d-matrix-ii/

    Algorithm

    1. At each iteration, eliminate either a row or a column.
    2. Complexity will be O(M+N).
    class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            M = len(matrix)
            if M == 0:
                return False
            N = len(matrix[0])
            if N == 0:
                return False
            rs, ce = 0, N-1
            while rs < M and ce > -1:
                if target == matrix[rs][ce]:
                    return True
                elif target < matrix[rs][ce]:
                    ce = ce - 1
                else:
                    rs = rs + 1
            return False
    

Log in to reply
 

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