The Matrix Find Algorithm in Python

What is the output of this code snippet?

def matrixFind(matrix, value):
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
i = 0
j = n - 1
while i < m and j >= 0:
if matrix[i][j] == value:
return True
elif matrix[i][j] < value:
i = i + 1
j = j - 1
return False

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

The challenge is shifting from understanding syntactical to semantical code snippets and algorithms.

If you thoroughly master these types of code puzzles, you will join the club of advanced coders. Thus, you open up the opportunity to work in one of the highest paid job industry in the world.

The algorithm in the puzzle is a beautiful way to search a value in a sorted matrix without visiting all values. 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. Do you see the importance of understanding the basics? The matrix is sorted as the integers in the rows and columns increase monotonically with the row and column number.

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

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

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.

Are you a master coder?
Test your skills now!

Related Video



Leave a Comment

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