Matrix: Set a row/col to zero

Question

A practice interview question:

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

void SetZeroOnMatrix(int **matrix, int M, int N)
{
    bool *rowZeros = new bool[M];
    bool *colZeros = new bool[N];

    // Find the 0's
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(matrix[i][j] == 0)
            {
                rowZeros[i] = false;
                colZeros[j] = false;
            }
        }
    }

    // Replace the values
    for(int i =0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(!rowZeros[i]||!colZeros[j])
                matrix[i][j]=0;
        }
    }

    delete[](rowZeros);
    delete[](colZeros);
}

If \$N = M\$, I'm assuming that this would have a time complexity of \$O(N^2)\$ and a space complexity of \$O(N)\$.

Answer 1

Don't dynamically allocate objects if you don't need to.

bool *rowZeros = new bool[M];
bool *colZeros = new bool[N];

If you do it this way you need to take control and do manual memory management (a bad idea).

Most specifically your code is not exception safe. If your code or anything you called throws an exception you leak memory (OK so this function is simplistic enough that it is unlikely but code has a tendency to evolve over time and you want to write code that is easy to maintain so writing it exception safe to begin with is a general goal).

Also C++ has a tendency to have early return backed into the code. This is because of automatic memory management that has been developed over the years. If somebody modifies your code to have an early return (say because they found no zero's on the first pass). Then your code is now likely to leak. So designing your code again t to use automatic memory management just makes your code more maintainable.

I would use a vector here:

std::vector<char> rowZeros(M, true);
std::vector<char> colZeros(N, true);

This allocates memory. But when the function exits all memory is correctly deallocated (even after early return or exception). Use standard container like automatic variables whenever you can.

Notice I did not use std::vector<bool>. Normally I would use the same type in the vector that I would have used in the array. But there is special consideration taken for std::vector<bool> that make it less efficient (everybody has concluded this was a mistake by the committee but it is not going to be fixed for backwards compatibility (at least not any time soon)).

Also note your original code contains a bug:

bool *rowZeros = new bool[M];  // This allocates the array but does not initialize.

Because the array is not initialized reading the elements is undefined behavior (until after they have been initialized). You could have initialized them to zero(false) with:

bool *rowZeros = new bool[M]();
                       //   ^^  forces zero initialization of all members.

But the vector constructor has a more obvious way of doing it.

std::vector<char> rowZeros(M, true);
                    //     ^               Size
                    //        ^^^^         Value copied into each cell of the vector.