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))
# TrueIf 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.
- The top right matrix value
matrix[i][j]is equal to the searched value. In this case, the algorithm returnsTrue. - 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 rowi = i+1. Next, we repeat this procedure with a smaller matrix that has one row less (i.e., row i). - 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 decreasingj = 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
Programmer Humor
There are only 10 kinds of people in this world: those who know binary and those who don’t.
👩🧔♂️
~~~
There are 10 types of people in the world. Those who understand trinary, those who don’t, and those who mistake it for binary.
👩🧔♂️👱♀️
Where to Go From Here?
Enough theory. Let’s get some practice!
Coders get paid six figures and more because they can solve problems more effectively using machine intelligence and automation.
To become more successful in coding, solve more real problems for real people. 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?
You build high-value coding skills by working on practical coding projects!
Do you want to stop learning with toy projects and focus on practical code projects that earn you money and solve real problems for people?
🚀 If your answer is YES!, consider becoming 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.
If you just want to learn about the freelancing opportunity, feel free to watch my free webinar “How to Build Your High-Income Skill Python” and learn how I grew my coding business online and how you can, too—from the comfort of your own home.