Problem: Set Matrix Zeros

Given an m x n matrix, if an element in the matrix is 0, set its entire row and entire column to 0. You need to perform this operation in place and without using extra space.

Example:

Input:

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

Output:

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

Approach:

1. Traverse through the matrix to identify the rows and columns that need to be set to zero.
2. For each zero, mark the row and column as needing to be set to zero.
3. Once this marking is complete, set the appropriate rows and columns to zero.
4. Ensure that you do this in place, without using extra space for a second matrix.

C Code Solution:

#include <stdio.h>

#define ROWS 3
#define COLS 3

void setZeroes(int matrix[ROWS][COLS]) {
    int rowFlag = 0, colFlag = 0;

    // Check if first row has any zeros
    for (int i = 0; i < COLS; i++) {
        if (matrix[0][i] == 0) {
            rowFlag = 1;
            break;
        }
    }

    // Check if first column has any zeros
    for (int i = 0; i < ROWS; i++) {
        if (matrix[i][0] == 0) {
            colFlag = 1;
            break;
        }
    }

    // Use the first row and first column to mark the zeroes in the rest of the matrix
    for (int i = 1; i < ROWS; i++) {
        for (int j = 1; j < COLS; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;  // Mark row
                matrix[0][j] = 0;  // Mark column
            }
        }
    }

    // Set matrix elements to zero using the first row and column markers
    for (int i = 1; i < ROWS; i++) {
        for (int j = 1; j < COLS; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // Set first row to zero if needed
    if (rowFlag == 1) {
        for (int i = 0; i < COLS; i++) {
            matrix[0][i] = 0;
        }
    }

    // Set first column to zero if needed
    if (colFlag == 1) {
        for (int i = 0; i < ROWS; i++) {
            matrix[i][0] = 0;
        }
    }
}

void printMatrix(int matrix[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("n");
    }
}

int main() {
    int matrix[ROWS][COLS] = {
        {1, 1, 1},
        {1, 0, 1},
        {1, 1, 1}
    };

    printf("Original Matrix:n");
    printMatrix(matrix);

    setZeroes(matrix);

    printf("nMatrix After Setting Zeros:n");
    printMatrix(matrix);

    return 0;
}

Explanation of Code:

1. Initial Check for First Row and First Column:

   • We first check if the first row or first column contains any zeros. If so, we use rowFlag and colFlag to mark that we need to set the entire row or column to zeros.

2. Marking Zeros:

   • For the rest of the matrix, we use the first row and the first column as markers. If matrix[i][j] is zero, we mark matrix[i][0] and matrix[0][j] by setting them to zero.

3. Setting Zeros:

   • We then go through the matrix and use the markers in the first row and column to set the appropriate elements to zero.

4. Setting First Row and First Column:

   • Finally, we handle setting the first row and the first column to zero if needed, based on the flags.

Time and Space Complexity:

• Time Complexity: O(m×n)O(m times n), where mm and nn are the number of rows and columns, respectively. We traverse the matrix a few times, but each traversal is linear.
• Space Complexity: O(1)O(1) extra space, as we only use a few extra variables (rowFlag and colFlag) and modify the matrix in place.

Example Walkthrough:

Input:

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

• Initially, rowFlag = 0 and colFlag = 0.
• During the traversal, we find that matrix[1][1] == 0, so we mark matrix[1][0] and matrix[0][1] to be zero.
• After the second pass, the matrix will have rows and columns updated accordingly.

Output:

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