The Matrix Find Algorithm in Python

Challenge: How to find an element in a sorted matrix where row and column values increase monotonically?

What is a matrix? A matrix is a table of values consisting of rows and columns. Here, we represent the matrix as a list of integer lists. Hence, we can access matrix values with the indexing and slicing notation.

How to Find an Element in a Matrix in Python?

The naive algorithm to find an element in a Python matrix is to iterate over all rows and values in that rows and compare these elements to the searched value:

def matrix_find(matrix, value):
    for row in matrix:
        for element in row:
            if element == value:
                return True
    return False
            

matrix = [[3, 4, 4, 6],
          [6, 8, 11, 12],
          [6, 8, 11, 15],
          [9, 11, 12, 17]]

print(matrix_find(matrix, 7))
# False

print(matrix_find(matrix, 17))
# True

If the matrix has n rows and m columns, the runtime complexity of the algorithm is O(n*m) because you have to perform n*m comparisons. This is not optimal for a sorted matrix (see next)!

How to Find an Element in a Sorted Matrix in Python?

What is a sorted matrix? The matrix is sorted as the integers in the rows and columns increase monotonically with the row and column number.

The matrix-find algorithm is a beautiful way to search a value in a sorted matrix without visiting all values in the sorted matrix.

Here’s the algorithm:

def matrix_find(matrix, value):
    if not matrix or not matrix[0]:
        return False

    j = len(matrix) - 1
    for row in matrix:
        while row[j] > value:
            j = j - 1
            if j == -1:
                return False
        if row[j] == value:
            return True
    return False

matrix = [[3, 4, 4, 6],
          [6, 8, 11, 12],
          [6, 8, 11, 15],
          [9, 11, 12, 17]]
print(matrix_find(matrix=matrix, value=7))

The function matrixFind takes a sorted integer matrix and an integer value. It returns True if the matrix contains the integer value.

Explanation

In the first few lines, the algorithm checks whether the matrix is empty and returns False if this is the case.

Then, the while loop iterates over rows i and column j of the matrix starting with the first row i=0 and the last column j=n-1.

But instead of searching the whole matrix, the algorithm uses a smarter strategy. It skips whole rows and columns at a time with the following method.

Check the last value of the first row (top right matrix value). We denote this value as matrix[i][j]. There are three cases.

  1. The top right matrix value matrix[i][j] is equal to the searched value. In this case, the algorithm returns True.
  2. The top right matrix value matrix[i][j] is smaller than the searched value. Because the matrix is sorted, the top right matrix value is the largest element in the row i. Thus, we can skip row i completely by going to the next row i = i+1. Next, we repeat this procedure with a smaller matrix that has one row less (i.e., row i).
  3. The top right matrix value matrix[i][j] is larger than the searched value. This means that the whole column j has only elements that are larger than the searched value. Thus, we are sure that our searched value is not in column j and we can skip this column completely by decreasing j = j-1. Next, we repeat this procedure with a smaller matrix that has one column less (i.e., row j).

Runtime Complexity Matrix-Find

In summary, the idea of this great algorithm from Keith Schwartz reduces one row or one column in each iteration. The runtime is only O(2n) instead of O(n^2) for a squared matrix with n rows and columns.

Puzzle Matrix-Find

Test your understanding by solving the following Python puzzle on our Finxter app:


Are you a master coder?
Test your skills now!

Related Video

Where to Go From Here?

Enough theory, let’s get some practice!

To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?

Practice projects is how you sharpen your saw in coding!

Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?

Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.

Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.

Join the free webinar now!

Leave a Comment

Your email address will not be published. Required fields are marked *