CareerCup1.7.cpp

CareerCup1.7.cpp

/* Chapter 1
 * 1.7 Write a algotithm such that if an element in an M*N matrix is 0, its entire
 * row and column are set to 0.
 */

#include <iostream>

using namespace std;

#define M 4
#define N 5

// Time Complexity: O(M*N)  Space Complexity: O(M+N)
void setZero(int matrix[][N])
{
    // Tracking row and column
    bool row[M] = {false};
    bool col[N] = {false};
    // Find 0
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (matrix[i][j] == 0)
            {
                row[i] = true;
                col[j] = true;
            }
        }
    }
    // Set row to 0
    for (int i = 0; i < M; ++i)
    {
        if (row[i] == true) {
            for (int j = 0; j < N; ++j) {
                matrix[i][j] = 0;
            }
        }
    }
    // Set column to 0
    for (int j = 0; j < N; ++j)
    {
        if (col[j] == true) {
            for (int i = 0; i < M; ++i) {
                matrix[i][j] = 0;
            }
        }
    }
    
}

// Main Function
int main(int argc, char const *argv[])
{
    int matrix [M][N] = {{1, 2, 7, 9, 2}, {3, 0, 8, 7, 4}, {6, 9, 0, 5, 6}, {9, 8, 9, 7, 1}};
    setZero(matrix);
    // Print out
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cout << matrix[i][j] << "  ";
        }
        cout << endl;
    }
    return 0;
}