240. Search a 2D Matrix II

Medium

Problem:

Implement an efficient algorithm to find a value in an $m\times{n}$ matrix. The matrix is sorted in ascending order from left to right and from top to bottom.

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

https://leetcode.com/problems/search-a-2d-matrix-ii/

What to learn:

Built-in Python functions: any() and all()

• any(): It's similar to the logical OR operation.

• all(): It's similar to the logical AND operation.

>>> any([True, False, False])
True

>>> all([True, True, True])
True

Start with the last element of the first row. If the target is smaller than this, move to the left. If it's larger, move downward.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        row = 0
        col = len(matrix[0]) -1

        while row <= len(matrix) - 1 and col >= 0:
            if target == matrix[row][col]:
                return True
            elif target < matrix[row][col]:
                col -= 1
            elif target > matrix[row][col]:
                row += 1
        return False

We can also start the search from the bottom-left corner of the matrix. At each step, the idea is to move either upward (if the current element is less than the target) or to the right (if the current element is greater than the target).

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        row = len(matrix) - 1
        col = 0

        while row >= 0 and col <= len(matrix[0]) -1:
            if target == matrix[row][col]:
                return True
            elif target > matrix[row][col]:
                col += 1
            elif target < matrix[row][col]:
                row -= 1
        return False

Pythonic way

Internally, Python will likely search the matrix for the presence of a value, one row at a time from the top.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        return any(target in row for row in matrix)