[Ninja Algorithm] From mine sweeping game to matrix operation: Exploring the problem of matrix zeroing

From minesweeping games to matrix operations: Exploring matrix zeroing problem

Algorithms in life

Imagine you are playing a mine-sweeping game. When you click on a mine, not only will the grid be marked, but the grids that are in the same column as it will also be affected. Or imagine an office seating table. If an infected person is found at a certain location, for safety reasons, the entire row (same row of colleagues) and the entire row (opposite colleagues) of the employee need to be marked as close contacts and need to be tested.

This kind of "one-spot trigger, full-row response" scenario is very common in life:

In the school curriculum, if a teacher takes leave, the entire line of courses needs to be adjusted.
In the table processing software, adjust the format of a certain cell, and set the entire row and column in a unified manner.
In the theater seat selection system, if a seat is damaged, the reservation function of that row and that column may be locked.

Problem description

LeetCode Question 73 "Matrix zero" is described as follows: Given a matrix of m x n, if an element is 0, set all elements of its row and column to 0. Please use the in-place algorithm.

For example:

Input: matrix = [
   [1,1,1],
   [1,0,1],
   [1,1,1]
 ]
 Output:[
   [1,0,1],
   [0,0,0],
   [1,0,1]
 ]

The most intuitive solution: extra space marking

Just like when dealing with epidemic prevention in the office, you first use a new table to record all the locations that need to be tested, and then handle them in a unified manner.

Let's use a simple example to understand:

Original matrix:
 [1,2,0]
 [3,4,5]

 1. Record the location of 0:
    - Row 0, column 2 has 0

 2. Mark the rows and columns that need to be zeroed:
    - Lines that need to be zeroed: [0]
    - Columns that need to be zeroed: [2]

 3. Modify the matrix according to the record:
    [0,0,0] // Line 0 sets zero
    [3,4,0] // Column 2 is zeroed

Optimization solution: In-place marking

If you think about it carefully, you will find that we can record marking information with the first row and first column of the matrix, just like using notepads on the wall of an office to mark the area that needs to be processed. This way there is no need for extra space.

Principle of in-place marking

First record whether the first row and the first column originally contain 0
Use the first row and the first column as marking board
Process the remaining matrix
Finally, process the first row and the first column according to the first step of the record

Sample Demo

Use the following matrix to illustrate:

[1,2,3]
 [4,0,6]
 [7,8,9]

 1. Record the status of the first row and the first column:
    - No 0 in the first line
    - No 0 in the first column

 2. Mark with the first row and the first column:
    - Because matrix[1][1]=0, so:
      - Mark the first line: matrix[0][1]=0
      - Tag the first column: matrix[1][0]=0

 3. Process the matrix body according to the marker:
    [1,0,3]
    [0,0,0]
    [7,0,9]

 4. Finally, process the first row and the first column according to the first step of the record

Java code implementation

public void setZeroes(int[][] matrix) {
     if (matrix == null || == 0) return;
    
     int m = ;
     int n = matrix[0].length;
    
     // Record whether the first row and the first column originally contain 0
     boolean firstRowHasZero = false;
     boolean firstColHasZero = false;
    
     // Check the first line
     for (int j = 0; j < n; j++) {
         if (matrix[0][j] == 0) {
             firstRowHasZero = true;
             break;
         }
     }
    
     // Check the first column
     for (int i = 0; i < m; i++) {
         if (matrix[i][0] == 0) {
             firstColHasZero = true;
             break;
         }
     }
    
     // Use the first row and the first column as markers
     for (int i = 1; i < m; i++) {
         for (int j = 1; j < n; j++) {
             if (matrix[i][j] == 0) {
                 matrix[i][0] = 0; // Mark the line
                 matrix[0][j] = 0; // Mark this column
             }
         }
     }
    
     // Process parts that are not first row and first column according to the mark
     for (int i = 1; i < m; i++) {
         for (int j = 1; j < n; j++) {
             if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                 matrix[i][j] = 0;
             }
         }
     }
    
     // Process the first line
     if (firstRowHasZero) {
         for (int j = 0; j < n; j++) {
             matrix[0][j] = 0;
         }
     }
    
     // Process the first column
     if (firstColHasZero) {
         for (int i = 0; i < m; i++) {
             matrix[i][0] = 0;
         }
     }
 }

Solution comparison

Let's compare these two methods:

Additional space marking:

Time complexity: O(m×n)
Space complexity: O(m+n)
Advantages: clear thinking and simple implementation
Disadvantages: Additional space is required

Place mark:

Time complexity: O(m×n)
Space complexity: O(1)
Advantages: No extra space required
Disadvantages: The implementation is slightly complicated and requires additional recording of the state of the first row and column.

Summary of problem solving skills

This question gives us inspiration:

In matrix problems, the matrix itself can often be used to store information.
When dealing with special cases (such as the first row) you can consider it separately
Handling complex problems in steps can make your thinking clearer
When modifying data, pay attention to protecting original information

summary

Through the question of matrix zeroing, we learned how to skillfully use the matrix itself to store information and avoid using extra space. This way of thinking is not only suitable for this question, but is very inspiring when dealing with matrix problems that require on-site modification of data. Remember, when encountering the problem of needing to mark information in a matrix, consider whether you can use certain locations in the matrix itself to store the mark!

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

Complete GitHub project