A O(m+n) Shrinkage Method


  • 0
    R
    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.


  • 0

    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.


  • 0
    R
    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.


  • 1

    @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.


  • 0
    R

    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


Log in to reply
 

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