[LeetCode] 74. Search a 2D Matrix

Question.

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 1:

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

Example 2:

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

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

My Solution

시간 복잡도를 고려하여 binary search 알고리즘을 활용하여 푼다.

from bisect import bisect_left
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            idx = bisect_left(row, target)
            if idx < len(row) and row[idx] == target:
                return True
            else: continue
        return False

• bisect_left 함수의 경우 타겟값을 못찾아도 None이나 -1을 뱉지 않으므로, 해당하는 조건이 맞을 때에만 True반환
  • 아니면 다음 row 확인