Space
Open
From Fieldwork
Scales
Archive
The most optimal approach treats the 2D matrix as a flattened 1D sorted array. Because the first integer of each row is greater than the last integer of the previous row, the entire matrix is monotonic.
We can use Binary Search with a coordinate transformation.
class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
if not matrix:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
# Convert 1D index 'mid' to 2D coordinates
row = mid // n
col = mid % n
guess = matrix[row][col]
if guess == target:
return True
elif guess < target:
left = mid + 1
else:
right = mid - 1
return FalsePractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode