Introduction

Arrays are fundamental data structures widely used in computer science and programming. One intriguing problem that often surfaces when dealing with arrays is the “Set Matrix Zero” problem. This problem challenges programmers to devise an efficient algorithm to set entire rows and columns to zero based on the presence of a zero in a matrix. In this chapter we will delve deep into the problem, understand and explore an effective algorithm to solve it.

Problem Understanding

Consider a matrix:

1 2 3
4 0 6
7 8 9

In this example, the element at the second row and second column is zero. According to the Set Matrix Zero problem, if any element in the matrix is zero, the entire row and column containing that element should be set to zero. Applying this rule to our example, the modified matrix should look like this:

1 0 3
0 0 0
7 0 9

The challenge lies in achieving this without utilizing additional memory, thereby maintaining the integrity of the original matrix.

Algorithm

To tackle this problem, we can follow a straightforward algorithm. We traverse the matrix, identify the cells containing zeroes, and use the first row and first column to mark the corresponding rows and columns that need to be zeroed out. However, since the first row and first column are used as markers, we need to handle them separately.

1. Traverse the matrix and mark the first row and first column based on zero elements.
2. Iterate through the matrix again, setting the entire row and column to zero if the corresponding first row or first column is marked.
3. Finally, check if the first row and first column need to be zeroed out and update accordingly.

Code Implementation

#include <iostream>
#include <vector>

using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    bool firstRowZero = false;
    bool firstColZero = false;

    // Check if the first row needs to be zeroed out
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }

    // Check if the first column needs to be zeroed out
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }

    // Mark the first row and first column based on zero elements
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Set entire rows and columns to zero based on first row and first column markers
    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;
            }
        }
    }

    // Update the first row if needed
    if (firstRowZero) {
        for (int j = 0; j < n; ++j) {
            matrix[0][j] = 0;
        }
    }

    // Update the first column if needed
    if (firstColZero) {
        for (int i = 0; i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
}

int main() {
    // Example usage
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 0, 6},
        {7, 8, 9}
    };

    setZeroes(matrix);

    // Display the modified matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Complexity Analysis

• Time Complexity: O(m * n) - We traverse the entire matrix twice.
• Space Complexity: O(1) - No additional space is used, meeting the requirement of the problem.