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 step-by-step guide:

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

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

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

  4. 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_first_row = any(matrix[0][j] == 0 for j in range(n))
        zero_first_column = any(matrix[i][0] == 0 for i in range(m))

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if zero_first_row:
            for j in range(n):
                matrix[0][j] = 0

        if zero_first_column:
            for i in range(m):
                matrix[i][0] = 0

Explanation:

  • The variables zero_first_row and zero_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 in-place 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”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        # input validation
        if not matrix:
            return []

        m = len(matrix)
        n = len(matrix[0])

         zeroes_row = [False] * m
         zeroes_col = [False] * n
         for row in range(m):
             for col in range(n):
                 if matrix[row][col] == 0:
                     zeroes_row[row] = True
                     zeroes_col[col] = True

         for row in range(m):
             for col in range(n):
                 if zeroes_row[row] or zeroes_col[col]:
                     matrix[row][col] = 0

Problem Classification

Language Agnostic Coding Drills

  1. Understanding basic data types: integers, boolean, lists
  2. Understanding nested lists (matrices)
  3. Understanding basic arithmetic operations like addition, subtraction
  4. Understanding if-else conditionals
  5. Understanding loops: for loop, nested loops
  6. Understanding array/list indexing and index-based operations
  7. Understanding how to define a function in Python
  8. Problem-specific: 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 in-place, optimizing space usage while accomplishing the task.

Here is a potential arrangement of the drills in increasing order of difficulty:

  1. Understanding basic data types: integers, boolean, lists
  2. Understanding basic arithmetic operations like addition, subtraction
  3. Understanding if-else conditionals
  4. Understanding loops: for loop, nested loops
  5. Understanding array/list indexing and index-based operations
  6. Understanding how to define a function in Python
  7. Understanding nested lists (matrices)
  8. Problem-specific: Implementing a function to set entire row and column to zeroes in a matrix

Targeted Drills in Python

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

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

  3. Understanding if-else conditionals

    Here, the task is to use an if-else 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")

  4. Understanding loops: for loop, nested loops

    Here, the task is to print the numbers 0-4 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()

  5. Understanding array/list indexing and index-based 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)

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

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

  8. Problem-specific: 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.