Search A 2d Matrix Ii - Leetcode Solution

Problem Statement: Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties: • Integers in each row are sorted in ascending from left to right. • Integers in each column are sorted in ascending from top to bottom.

Example 1: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

Example 2: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false

Approach: We can solve the problem using a binary search approach as the given matrix has sorted rows and columns. • We start at the top-right corner of the matrix (element matrix[0][n-1]). This element is the largest element in the first row and the smallest element in the last column. • If the target value is less than the current element, we move one step left (since the current element is the largest element in this column). • If the target value is greater than the current element, we move one step down (since the current element is the smallest element in this row). • We repeat this process until we find the target element or get out of bounds of the matrix.

Let's see the implementation.

Code:

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: # return false for empty matrices if len(matrix) == 0 or len(matrix[0]) == 0: return False

    # set initial indices
    row, col = 0, len(matrix[0])-1
    
    # looping over the matrix
    while row < len(matrix) and col >= 0:
        # if target is found, return True
        if matrix[row][col] == target:
            return True
        # if target is lesser than current element, move left
        elif matrix[row][col] > target:
            col -= 1
        # if target is greater than current element, move down
        else:
            row += 1
    # return False if target is not found
    return False

Time Complexity Analysis: The time complexity of the searchMatrix function is O(m+n), where m is the number of rows in the matrix and n is the number of columns in the matrix. This is because, in the worst case, we may have to traverse all the rows and columns in the matrix to find the target element.

Space Complexity Analysis: The space complexity of the searchMatrix function is O(1) because we are not using any extra space. We are only using the existing input matrix to perform the search.

1