An Intro to Python 3/

...

/

Puzzles 31 to 33

Puzzles 31 to 33

Learn about different algorithms in Python like maximum profit algorithm, bubble sort algorithm, and searching a sorted matrix.

We'll cover the following...

Puzzle 31

What is the output of the following code?

Note: Enter the output you guessed. Then, press the Run button, and your new Elo will be calculated. Don’t forget to save your Elo rating.

Press + to interact
Elo
1000
#############################
## id 112
## Puzzle Elo 1353
## Correctly solved 41 %
#############################
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=11))

Enter the input below

Searching a sorted matrix

A matrix is a table of values consisting of rows and columns.

This puzzle represents it as a list of integer lists. Hence, we can access matrix values with the indexing and slicing notation. The matrix is sorted as the integers in the rows and columns increase monotonically with the row and column number. The function matrix_find takes a sorted integer matrix and an integer value. It returns True if the matrix contains the integer value. Otherwise, it returns False.

In the first two lines, the algorithm checks whether the matrix is empty and returns False if this is the case. Then, the for loop iterates over the matrix’s rows, starting with the first row. But instead of searching the whole matrix, the algorithm uses a smarter strategy. It skips whole rows and columns using the sorted property. The algorithm starts with the first row and the last column j = len(matrix) - 1. Then, it skips one column at a time by decreasing the parameter j monotonically (j = j - 1).

Why can it skip the whole column?

It can skip the whole row because as long as the column value row[j] is larger than the searched value value ...