LeetCode 74: Search A 2d Matrix — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Binary Search | Matrix | Array

The Problem

Given a 2D matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, determine if a target value exists in the matrix.

Approach

Treat the 2D matrix as a flattened 1D sorted array and apply binary search. Use mathematical operations to convert between 1D index and 2D coordinates: row = mid // cols and col = mid % cols.

Time: O(log(m*n)) · Space: O(1)

Code

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        rows, cols = len(matrix), len(matrix[0])
        left, right = 0, rows * cols - 1

        while left <= right:
            mid = left + (right - left) // 2
            num = matrix[mid // cols][mid % cols]

            if num == target:
                return True
            elif num < target:
                left = mid + 1
            else:
                right = mid - 1

        return False