Leetcode 74: Search a 2D Matrix

By /

The original question can be found here.

The question is asking us to find the target element in a 2-dimensional array. Each row is greater than the row above it. Within each row, elements are sorted as well.

Brute Force

We scan row by row to find the target element:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row, row_array in enumerate(matrix):
            for col, element in enumerate(row_array):
                if target == matrix[row][col]:
                    return True

        return False

Time Complexity: O(m * n), where m is number or rows, and n is number of columns. Space Complexity: O(1).

Binary Search

If you’re not familiar with binary search, please visit my post here. We can still perform binary search on 2 dimensional array. The only hard part is how to convert 1d index to 2d. Let’s say number of rows is m, and number of columns is n. If we map a 1d index to 2d, it’s [i / n][i % n]. 

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        num_of_rows, num_of_cols = len(matrix), len(matrix[0])
        left, right = 0, num_of_rows * num_of_cols - 1
        while left + 1 < right:
            mid = (left + right) // 2
            row, col = mid // num_of_cols, mid % num_of_cols
            if matrix[row][col] == target:
                return True
            if matrix[row][col] < target:
                left = mid
            else:
                right = mid
        if matrix[left // num_of_cols][left % num_of_cols] == target:
            return True
        if matrix[right // num_of_cols][right % num_of_cols] == target:
            return True
        return False

Time Complexity: O(log(m*n)). Space Complexity: O(1).

Scroll to Top