Leetcode # 74. Search a 2D Matrix

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

Solution

m := len(matrix)
n := len(matrix[0])

Time Complexity: O(m + log(n)) > O(log(m) + log(n)) = O(log(m * n))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    for row in matrix:
      if target > row[-1]:continue

      # binary search
      left, right = 0, len(row) - 1
      while left <= right:
        middle = (left + right) // 2
        if row[middle] == target: return True
        if row[middle] < target:
          left = middle + 1
        else:
            right = middle - 1
    
      return False
    return False

Better Solution

Time Complexity: O(log(m * n))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # binary search
    left, right = 0, len(matrix) * len(matrix[0]) - 1
    while left <= right:
      middle = (left + right) // 2
      if matrix[middle // len(matrix[0])][middle % len(matrix[0])] == target: return True
      if matrix[middle // len(matrix[0])][middle % len(matrix[0])] < target:
        left = middle + 1
      else:
          right = middle - 1
    
    return False

Last Updated on 2023/08/16 by A1go