240: Time 91.4% and Space 98.52%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe problem can be solved using a divide and conquer approach. We start f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe problem can be solved using a divide and conquer approach. We start from the top right corner and move towards the bottom left corner of the matrix. At each position, we check if the current element is equal to the target value. If it is equal, we return True. If it is less than the target value, we move down one row because all the elements in the current row are smaller than the current element. If it is greater than the target value, we move left one column because all the elements in the current column are greater than the current element.\n\nThe time complexity of this algorithm is O(m+n) because in the worst case scenario we traverse all rows and columns. The space complexity is O(1) because we are not using any extra data structure.\n\n# Complexity\n- Time complexity:\n91.4%\n\n- Space complexity:\n98.52%\n\n# Code\n```\nclass Solution:\n    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n        # set initial position to top right corner\n        row, col = 0, len(matrix[0])-1\n        \n        while row < len(matrix) and col >= 0:\n            if matrix[row][col] == target:\n                # target found\n                return True\n            elif matrix[row][col] < target:\n                # current element is smaller than target, move down one row\n                row += 1\n            else:\n                # current element is greater than target, move left one column\n                col -= 1\n                \n        # target not found\n        return False\n\n```
['Array', 'Binary Search', 'Divide and Conquer', 'Python', 'Python3']