# A O(m+n) Shrinkage Method

• ``````def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if matrix:
row_start, row_end = 0, len(matrix) - 1
col_start, col_end = 0, len(matrix[0]) - 1
last_block_size = (row_end - row_start + 1) * (col_end - col_start + 1)
try:
while True:
while matrix[row_start][col_end] < target: # if the last element of the row is smaller than target , the entire row is smaller than target
row_start += 1
while matrix[row_end][col_start] < target: # if last element of column is smaller than target, the entire column is smaller than target
col_start += 1
while matrix[row_start][col_end] > target: # if the first element of the column is larger than target, the entire column is larger than target
col_end -= 1
while matrix[row_end][col_start] > target: # if the first element of the row is larger than target, the entire row is larger than target
row_end -= 1
if row_start > row_end or col_start > col_end:
return False
block_size = (row_end - row_start + 1) * (col_end - col_start + 1)
if block_size == last_block_size:  # which means at least one corner is neither larger than target nor smaller than target
return True
else:
last_block_size = block_size
except IndexError:
return False
else:
return False
``````

The strategy is to narrow down the size of block, where the target may be located.

• I don't see how you'd generalize it to more dimensions. Can you show it for 3D?

Also, time complexity O((logm)^2 + (logn)^2) is impossible.

• ``````def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[List[int]]]
:type target: int
:rtype: bool
"""
if matrix:
row_start, row_end = 0, len(matrix) - 1
col_start, col_end = 0, len(matrix[0]) - 1
z_start, z_end = 0, len(matrix[0][0]) - 1
last_block_size = (row_end - row_start + 1) * (col_end - col_start + 1) * (z_end - z_start + 1)
try:
while True:
while matrix[row_start][col_end][z_end] < target:
row_start += 1
while matrix[row_end][col_start][z_end] < target:
col_start += 1
while matrix[row_end][col_end][z_start] < target:
z_start += 1
while matrix[row_start][col_end][z_start] > target:
col_end -= 1
while matrix[row_end][col_start][z_start] > target:
row_end -= 1
while matrix[row_start][col_start][z_end] > target:
z_end -= 1
if row_start > row_end or col_start > col_end or z_start > z_end:
return False
block_size = (row_end - row_start + 1) * (col_end - col_start + 1) * (z_end - z_start + 1)
if block_size == last_block_size:  # which means at least one corner is neither larger than target nor smaller than target
return True
else:
last_block_size = block_size
except IndexError:
return False
else:
return False
``````

Simply add z axis into the loop. And I mean when you replace the inner while with binary search algorithm, time complexity will be reduced, it will be possible, but for small matrix, no need to apply the method.

• @rongcheng Your 3D code says that `[[[0, 2], [2, 4]], [[2, 4], [4, 6]]]` contains `3`. That's wrong. Can you fix it?

Also, no, binary search won't give you that better runtime. Try for example matrix `[range(i, i+100, 2) for i in range(0, 100, 2)]` and target `101`. Your inner while-loops progress only a single step in each iteration of the outer while-loop. Binary search isn't going to do anything about that. It's only going to be slower.

• Sorry, it turn out to shrink the 3d matrix will be stuck when all the surfaces of the cube include both smaller and larger elements. I am trying to fix it. Thank you for reminding

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.