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.

If you think about it, this matrix is just a sorted list that’s been packed into a matrix. So if we were to just expand the matrix into a list, we could just apply binary search on that list. But we don’t need to do that, we can just apply binary search on the matrix itself. Since we can’t use regular list access, we’ll write a custom accessor that will take an index and return the value at that index in the matrix. The binary saerch itself will be unchanged.

Approach:

We need to find l and r for our search space. Well that’s, l = 0 and r = m*n - 1, where m is the number of rows and n is the number of columns. Then we can just apply binary search on the matrix. The only thing we need to do is write a custom accessor that will take an index and return the value at that index in the matrix.

The accessor will take an index and return the value at that index in the matrix. The index will be in the range of 0 to m*n - 1. We can get the row and column from the index using integer division and modulo respectively. The row will be index // n and the column will be index % n. Then we can return the value at that row and column in the matrix.

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.)

And we’re done!

Solution in Python


class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M = len(matrix)
        N = len(matrix[0])

        l, r = 0, M*N - 1

        def get(index):
            row = index // N
            col = index % N
            return matrix[row][col]

        while l <= r:
            m = (l + r) // 2
            v = get(m)

            if v == target:
                return True
            elif v < target:
                l = m + 1
            else:
                r = m - 1
        
        return False

Complexity

  • Time: $O(log(m*n))$
    Since we’re doing binary search on the matrix, the time complexity is logarithmic in the number of elements in the matrix, which is m*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.