Problem Statement in English

You are given an m x n integer matrix, so that’s mrows and n columns called matrix with 2 guarantees:

  • Each row is sorted in ascending order.
  • The first integer of each row is greater than the last integer of the previous row.

You need to find out if an integer target exists in the matrix. Return true if it does, else false.

Given an integer target, return true if target is in matrix or false otherwise.

And they want the time complexity to be $O(log(m * n))$. That’s a dead giveaway.

Intuition

Logarithmic time complexity? Ring a bell?

But before we get to that, let’s take a moment and realise that the columns are guaranteed to be sorted. Plus, in their own twisted way, so are the rows:

The first integer of each row is greater than the last integer of the previous row.

This is already a huge indication that we can apply binary search on this problem.

Approach:

  • Step 1.1: Find the relevant row
    We apply binary search on essentially the first column of the matrix, to find the row that we need to check.

  • Step 1.2: Find the relevant column
    Once we have the row, we apply binary search again, this time on that one row.

Now you might wonder, why not use linear search on the row? And in fact, with the constraints provided, you actually could. The column constraints are 1<= matrix[i] <= 100. There can only be 100 columns at the most. But 2 reasons not to:

  • Just, why? When the row is sorted, you can run, for example, 7 queries on 128 elements, instead of, well, 128! That’s a lot of savings!
  • They’ve specified the time complexity you need to achieve. (With that said, I noticed a lot of submissions on LeetCode that violated this and still passed. Bizarre.)

Solution in Python


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = self.findRow(matrix, target)

        if row == -1:
            return False

        # easy option, this will result in `O(n*log(n))`
        # return target in matrix[col]

        # slightly more involved, and results in `O(log(m)*log(n))`
        # check if `target` exists in that `row`
        col = self.findCol(
            matrix[row],
            target,
        )

        return True if col != -1 else False

    def findRow(self, matrix: List[List[int]], target: int) -> int:
        left, right = 0, len(matrix) - 1

        mid = right // 2

        while left <= right:
            # if the next row isn't a possible solution, then this row is what we're looking for
            if matrix[mid][0] <= target and matrix[mid + 1][0] > target:
                return mid
            # if the next row is also a possible solution, then this row isn't
            elif matrix[mid][0] < target and matrix[mid + 1][0] <= target:
                left = mid + 1
                mid = (left + right) // 2
            # if mid's too big, we want to dial it down
            elif matrix[mid][0] > target:
                right = mid - 1
                mid = (left + right) // 2

        # im returning -1 to indicate that such a row could not be found
        return -1

    def findCol(self, row: List[int], target: int) -> int:
        # the regular binary search with no extra conditions
        left, right = 0, len(row) - 1
        mid = right // 2

        while left <= right:
            if row[mid] == target:
                return mid
            elif row[mid] < target:
                left = mid + 1
                mid = (left + right) // 2
            elif row[mid] > target:
                right = mid - 1
                mid = (left + right) // 2

        return -1

Complexity

  • Time: $O(log(m)+log(n))$ = $O(log(m*n))$

We use $O(log(m))$ for locating the correct row $O(log(n))$ to locate the correct column, so that’s $O(log(m)+log(n))$.

  • Space: $O(1)$

Since we’re not using anyhing more than a few integers to point to places in the array, it’s constant space.

And we are done.