Matrix: Given a matrix, set it to zero

Problem Statement:

You are given a matrix.

You need to set the entire row and column as zero if an element is zero.

Example:

Input: 

[[2, -5, 1],
 [-3, 0, 1],
 [4, -6, 1]]

Output: 

[ [2, 0, 1],
  [0, 0, 0],
  [3, 0, 1]]

Solution 1: Bruteforce Approach

In this approach, we take additional matrix and copy all the elements from matrix 1 to matrix 2.

Then traverse the matrix, when we encounter 0, make the entire row and column of the matrix 2 to 0.

Then copy all the elements from matrix 2 to original matrix.

Time Complexity: O((mn)∗(m+n))
Space Complexity: O(mn)

Solution 2: Another Approach

Instead of taking a separate matrix, we will take 2 arrays, one for row and one for column.

Traverse the matrix if mat[i,j] = 0, then set row[i] = 0, col [j] = 0.

Then once its completed, update the mat[i][j] to 0.

Time Complexity: O(mn)
Space Complexity: O(m+n)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

void solution_2 (vector<vector<int>> &mat)
{

      int m = mat.size();
      int n = mat[0].size();

      vector<int> row(m, 1);
      vector<int> col(n, 1);

      for(int i=0;i<m;i++)
      {
          for(int j=0;j<n;j++)
          {
              if(mat[i][j]==0)
              {
                  row[i]=0;
                  col[j]=0;
              }
          }
      }
      
      for(int i=0;i<m;i++)
      {
          for(int j=0;j<n;j++)
          {
              if(row[i]==0 || col[j]==0)
                  mat[i][j]=0;
          }
      }
  }


void solution_1 (vector<vector<int>> &mat)
{

    int m= mat.size();
    int n= mat[0].size();

    vector<vector<int>> matrix2 = mat;

    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(mat[i][j]==0)
            {
                for(int k=0;k<n;k++)
                    matrix2[i][k]=0;

                for(int k=0;k<m;k++)
                    matrix2[k][j]=0;
            }
        }
    }

    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            mat[i][j]=matrix2[i][j];
    }
}

int main() {
    vector<vector<int> > mat = { { 2, -5, 1 },
                                 { -3, 0, 1 },
                                 { 4, -6, 1 } };

    solution_1(mat);
    for (int i = 0; i < mat.size(); i++) 
    {
        for (int j = 0; j < mat[0].size(); j++) 
        {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
    
    cout <<"=====================" <<endl;

    mat = { { 2, -5, 1 },
         { -3, 0, 1 },
         { 4, -6, 1 } };

    solution_1(mat);
    for (int i = 0; i < mat.size(); i++) 
    {
        for (int j = 0; j < mat[0].size(); j++) 
        {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
    

    return 0;
}

Output

2 0 1 
0 0 0 
4 0 1 
=====================
2 0 1 
0 0 0 
4 0 1