74. Search a 2D Matrix

Problem Statement

link: https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.cn/problems/search-a-2d-matrix/

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false

Solution Approach

Treat the 2D matrix as a flattened 1D array and perform a binary search on it.

Algorithm

1. Initialization: Determine the dimensions (m x n) of the matrix. Handle base cases like if the matrix is empty or if the target is out of the matrix’s bounds.
2. Row Identification: Create a list of the first elements in each row and use binary search on it to identify the potential row where the target might exist.
3. Element Search: Once the row is identified, use binary search again on that row to check if the target is present.
4. Return Result: If the target is found in the identified row, return True; otherwise, return False.

Implement

    class Solution:
        def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
          m, n = len(matrix), len(matrix[0])
          tmp = []
          if m == 0 or n == 0 or target < matrix[0][0] or target > matrix[m - 1][n - 1]:
              return False
          for i in range(m):
              tmp.append(matrix[i][0])
          idx = bisect.bisect_left(tmp, target)
          if idx == len(tmp) or matrix[idx][0] > target:
              idx -= 1
          idx2 = bisect.bisect_left(matrix[idx], target)
          if idx2 == n:
              return False
          return matrix[idx][idx2] == target

 

    
    

Twitter  facebook  Email