Set Matrix Zeroes - C Solution

1. Introduction

In this post, we tackle a common array manipulation challenge known as "Set Matrix Zeroes". This problem involves modifying a matrix in place based on certain conditions, specifically setting entire rows and columns to zero if an element in the matrix is zero. It's a useful exercise in understanding how to efficiently navigate and modify two-dimensional arrays in C.

Problem

Given an m x n integer matrix, the task is to set its entire row and column to zeros if an element is zero, and to do it in place.

2. Solution Steps

1. First, determine if the first row and first column need to be set to zeros.

2. Use the first row and first column as markers. If matrix[i][j] is zero, set matrix[i][0] and matrix[0][j] to zero.

3. Iterate over the matrix to mark the zeros in the first row and first column.

4. Iterate again to set the zeros for all rows and columns using the markers.

5. Finally, set the first row and first column to zeros if needed.

3. Code Program

#include <stdio.h>

// Function to set matrix zeroes
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int fr = 0, fc = 0;

    // Check if first row and column need to be zero
    for (int i = 0; i < matrixSize; i++) {
        if (matrix[i][0] == 0) {
            fr = 1;
        }
        for (int j = 0; j < matrixColSize[i]; j++) {
            if (matrix[i][j] == 0) {
                matrix[0][j] = matrix[i][0] = 0;
            }
        }
    }

    // Set matrix zeroes using first row and column
    for (int i = matrixSize - 1; i >= 0; i--) {
        for (int j = matrixColSize[i] - 1; j >= 1; j--) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
        if (fr) {
            matrix[i][0] = 0;
        }
    }
}

// Main function to test the setZeroes function
int main() {
    int matrix[3][4] = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
    int matrixColSize[] = {4, 4, 4};
    setZeroes((int**)matrix, 3, matrixColSize);

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Output:

0 0 0 0
0 4 5 0
0 0 0 0

Explanation:

1. Use the first row and column as markers for rows and columns that need to be set to zero.

2. Iterate over the matrix to set these markers.

3. Use the markers to set the appropriate rows and columns to zero.

4. Handle the first row and column separately if they contain a zero.

5. The main function tests the setZeroes function with a sample matrix and prints the modified matrix.