Set Matrix Zeroes

Problem Statement

In the given problem, we have a matrix of integers with dimensions m x n. Our task is to modify this matrix in such a way that if any element in the matrix is 0, then all the elements in its associated row and column should be set to 0. This transformation is to be done on the same matrix which means it must be done in place, without using any additional matrices for output.

The challenge not only lies in detecting the zeroes and modifying the corresponding rows and columns but also in ensuring that the modification doesn't inadvertently affect the process itself, as updating once could change the matrix prematurely.

Examples

Example 1

Input:

matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output:

[[1,0,1],[0,0,0],[1,0,1]]

Example 2

Input:

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Output:

[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

Approach and Intuition

To tackle this problem, the solution should efficiently navigate through the matrix to identify the locations of the zeros and then mark their respective rows and columns. The key is to achieve this without additional space proportional to the size of the matrix, which calls for clever use of the matrix itself to store the state information. Here’s a breakdown of how this can be approached:

1. Traverse the matrix to identify which rows and columns contain zeros.

   • This can be achieved by using the first row and the first column as indicators. If a row needs to be marked zeros, store this information in its corresponding element in the first column, and similarly use the elements of the first row to indicate the columns.

2. To avoid losing the data in the first row and the first column, use two variables to keep track if the original first row or first column had any zeros.

3. Start marking the internal cells only (skip the first row and first column), based on the state stored in the first row and the first column. By this point, modify the matrix safely assuming the marking won't prematurely affect other cells that are yet to be evaluated.

4. After all internal marking is done, use the information in the record variables to finally resolve the first row and the first column.

5. Scan through the first row. If it needs to be zeroed (based on the saved state), set all its elements to zero.

6. Similarly, modify the first column if required as per the saved state.

With constraints ensuring the bounds for m and n are within manageable limits (up to 200), this approach comfortably works within a reasonable time, while adhering to the in-place requirement thus minimizing additional space use - crucial, given the limitation set by the problem statement.

Solutions

class Solution {
public:
    void modifyMatrix(vector<vector<int>>& grid) {
        bool firstColumn = false;
        int totalRows = grid.size();
        int totalCols = grid[0].size();
    
        for (int row = 0; row < totalRows; row++) {
            if (grid[row][0] == 0) {
                firstColumn = true;
            }
            for (int col = 1; col < totalCols; col++) {
                if (grid[row][col] == 0) {
                    grid[0][col] = 0;
                    grid[row][0] = 0;
                }
            }
        }
    
        for (int row = 1; row < totalRows; row++) {
            for (int col = 1; col < totalCols; col++) {
                if (grid[row][0] == 0 || grid[0][col] == 0) {
                    grid[row][col] = 0;
                }
            }
        }
    
        if (grid[0][0] == 0) {
            for (int col = 0; col < totalCols; col++) {
                grid[0][col] = 0;
            }
        }
    
        if (firstColumn) {
            for (int row = 0; row < totalRows; row++) {
                grid[row][0] = 0;
            }
        }
    }
};