LC-0240 Medium LeetCode

240. Search a 2D Matrix II

Array Binary Search Divide and Conquer Matrix

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 55% Topics: Array, Binary Search, Divide and Conquer, Matrix

Reading material

Arrays & Hashing 12 min Binary Search 12 min Divide & Conquer 11 min

Reference solution (spoiler · python)

# Time:  O(m + n)
# Space: O(1)

class Solution(object):
    # @param {integer[][]} matrix
    # @param {integer} target
    # @return {boolean}
    def searchMatrix(self, matrix, target):
        m = len(matrix)
        if m == 0:
            return False

        n = len(matrix[0])
        if n == 0:
            return False

        i, j = 0, n - 1
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1

        return False

Solution from kamyu104/LeetCode-Solutions · MIT