Set Matrix Zeroes
This problem can be solved in place by using the first row and first column of the matrix as a marker for which rows and columns should be set to zero.
Here’s a stepbystep guide:
Check for Zeros in the First Row and Column: Determine if the first row and/or the first column should be set to zeros. Save this information for later.
Use the First Row and Column as Markers: Iterate through the rest of the matrix. If a cell has a value of 0, set the corresponding value in the first row and first column to 0.
Set Rows and Columns to Zero: Iterate through the first row and column. If a value is 0, set the entire corresponding row or column to zeros.
Handle the First Row and Column: Based on the information from step 1, set the first row and/or first column to zeros if needed.
Here’s the code implementing this approach:


Explanation:
 The variables
zero_first_row
andzero_first_column
determine if the first row and column should be set to zeros, respectively.  The first nested loop marks the rows and columns that should be set to zeros using the first row and column of the matrix.
 The second nested loop sets the marked rows and columns to zeros.
 The last two
if
conditions handle the first row and column based on the initial check.
The time complexity of this solution is (O(m \times n)), and the space complexity is (O(1)), as we are modifying the matrix in place.
Identifying Problem Isomorphism
“Set Matrix Zeroes” can be mapped to “Game of Life”.
In both problems, you’re given a 2D matrix and asked to modify the matrix based on conditions involving the current state of each cell.
In “Set Matrix Zeroes”, you traverse the matrix, and if you find a cell with a value of zero, you must set the entire corresponding row and column to zero.
In “Game of Life”, you again traverse the matrix, and modify the state of each cell based on the states of its neighboring cells. If a cell is ‘alive’ (value 1) and has fewer than two live neighbors, or has more than three live neighbors, it ‘dies’ (becomes 0). If a cell is ‘dead’ (value 0) and has exactly three live neighbors, it becomes ‘alive’ (value 1).
Both require careful handling of inplace matrix modifications, because modifications for one cell can affect the conditions for future cells. A common strategy to handle this is using different placeholder values to represent cells that have been modified.
“Set Matrix Zeroes” is a simpler problem because you only need to check if a cell’s value is zero, and then set its entire row and column to zero. “Game of Life” is more complex because you need to check each cell’s eight neighbors and count how many are ‘alive’, then modify the cell’s state based on these counts. However, the skills and strategies you use for “Set Matrix Zeroes” will certainly be helpful when tackling “Game of Life”.


Problem Classification
Language Agnostic Coding Drills
 Understanding basic data types: integers, boolean, lists
 Understanding nested lists (matrices)
 Understanding basic arithmetic operations like addition, subtraction
 Understanding ifelse conditionals
 Understanding loops: for loop, nested loops
 Understanding array/list indexing and indexbased operations
 Understanding how to define a function in Python
 Problemspecific: Implementing a function to set entire row and column to zeroes in a matrix
Here’s a detailed step by step approach to solving the problem:
This problem is an instance of the “space optimization problem”. The task is to set the entire row and column to zero if there’s a zero in a cell of a matrix. A simple solution is to keep a separate matrix of the same size and mark the rows and columns that should be set to zero. However, this requires extra space.
To optimize the space, we use two boolean arrays, zeroes_row
and zeroes_col
, to mark the rows and columns to be set to zero. The first nested loop in the solution goes through each cell of the matrix. If a cell is zero, it marks the corresponding entry in the zeroes_row
and zeroes_col
to be True.
The second nested loop then goes through each cell again, this time checking if the corresponding row or column has been marked True in the zeroes_row
or zeroes_col
. If it is, it sets the cell to 0. In this way, the function modifies the matrix inplace, optimizing space usage while accomplishing the task.
Here is a potential arrangement of the drills in increasing order of difficulty:
 Understanding basic data types: integers, boolean, lists
 Understanding basic arithmetic operations like addition, subtraction
 Understanding ifelse conditionals
 Understanding loops: for loop, nested loops
 Understanding array/list indexing and indexbased operations
 Understanding how to define a function in Python
 Understanding nested lists (matrices)
 Problemspecific: Implementing a function to set entire row and column to zeroes in a matrix
Targeted Drills in Python
Understanding basic data types: integers, boolean, lists
Here, the task is to create a variable for each type and print them.
1 2 3 4 5 6 7 8 9 10 11
# integers integer = 5 print(integer) # boolean boolean = True print(boolean) # lists list = [1, 2, 3, 4, 5] print(list)
Understanding basic arithmetic operations like addition, subtraction
Here, the task is to perform some basic arithmetic operations and print the results.
1 2 3 4 5 6 7 8
a = 7 b = 3 # addition print(a + b) # subtraction print(a  b)
Understanding ifelse conditionals
Here, the task is to use an ifelse conditional to check if a number is even or odd.
1 2 3 4 5 6
num = 4 if num % 2 == 0: print("Even") else: print("Odd")
Understanding loops: for loop, nested loops
Here, the task is to print the numbers 04 using a for loop, and then print a 2D array using a nested loop.
1 2 3 4 5 6 7 8 9 10
# for loop for i in range(5): print(i) # nested loop matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] for row in matrix: for item in row: print(item, end=" ") print()
Understanding array/list indexing and indexbased operations
Here, the task is to create a list, print the first item, change the second item, and print the whole list again.
1 2 3 4 5 6 7 8 9 10
list = [1, 2, 3, 4, 5] # print first item print(list[0]) # change second item list[1] = 20 # print whole list print(list)
Understanding how to define a function in Python
Here, the task is to define a function that adds two numbers and call it.
1 2 3 4
def add_numbers(a, b): return a + b print(add_numbers(3, 4))
Understanding nested lists (matrices)
Here, the task is to create a 2D list (matrix) and print it using a nested loop.
1 2 3 4 5
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] for row in matrix: for item in row: print(item, end=" ") print()
Problemspecific: Implementing a function to set entire row and column to zeroes in a matrix
Here, the task is to write a function that takes a matrix and two indices (row and column) as input and sets the entire row and column to zeros.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def set_zeroes(matrix, row, col): # set row to zeros for i in range(len(matrix[0])): matrix[row][i] = 0 # set column to zeros for i in range(len(matrix)): matrix[i][col] = 0 # define a matrix matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # set the first row and first column to zeros set_zeroes(matrix, 0, 0) # print the matrix for row in matrix: for item in row: print(item, end=" ") print()
In the above code, we define a function set_zeroes that takes a matrix and row and column indices. The function sets all elements in the specified row and column to zero. We then create a 3x3 matrix, set the first row and column to zeros by calling our set_zeroes function, and then print the resulting matrix to verify that the function works correctly.