Home » Interview coding problems/challenges

Set Matrix Zeroes

Set Matrix Zeroes: Given an mXn matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Submitted by Divyansh Jaipuriyar, on September 01, 2020

Problem statement:

Given an mXn matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Problem description:

The problem wants you to develop some logic such that all the elements of a certain row and column need to be changed to 0 if that position (row, col)==0. And leave other row and column as it is. The given problem needs that approach in which time complexity if constant that is without any extra space involved during the algorithm.

Input:

Given T number of test cases, each test case consists of matrix size mXn, m lines contain n elements either 1 or 0.

Output:

Print the final matrix after setting zeroes according to the question rule.

Examples:

Input:
T=1	
M=3,N=3
1 1 1
1 0 1
1 1 1

Output:
1 0 1
0 0 0
1 0 1

Solution Approach:

This problem asks you to solve in-place. It means you can only use constant extra space that is in O(1) space complexity.

We will use to boolean variable row and col variable which will be initially false. We will check each row and find if the first element of the given row is 0 or not. If 0 then we will assign row=true and break. Similarly, we will assign col variable with false initially and then we will make it true after checking it all column first elements. 

Now, we will travel all elements for the matrix except first row and first column and check if the current element is 0 or not. If 0 then we will make the first element of that column and row as 0.
We will again iterate through all elements of the matrix except first column and first row and check if the current element's first element in that column or the first element in that row is zero or not, if zero then we will make the current element as 0. 

Finally, if the row variable that we initially declare is true then we will make the first element of each row as 0, and if col variable is also true then we will make the first element of each col as 0. 

Time Complexity for above approach in worst case is (n*m)

Space complexity for above approach in worst case is O(1)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll arr[101][101];

#define N 101
//solve function which will take
//matrix and size of matrix as parameter.
void solve(ll A[N][N], ll m, ll n)
{
    //initialize boolean variable
    //row and col with false.
    bool row, col;
    row = false;
    col = false;

    //iterate through all the first
    //element of the row.
    for (ll i = 0; i < m; i++) {
        if (A[i][0] == 0) //found zero then break.
        {
            row = true;
            break;
        }
    }

    //iterate through all the first
    //element of the col.
    for (ll i = 0; i < n; i++) {
        if (A[0][i] == 0) //found zero then break.
        {
            col = true;
            break;
        }
    }

    //iterate all the elements of
    //the matrix except first row and col.
    for (ll i = 1; i < m; i++) {
        for (ll j = 1; j < m; j++) {
            //if zero then make first element
            //of its row and col as 0.
            if (A[i][j] == 0)
                A[i][0] = 0, A[0][j] = 0;
        }
    }

    //iterate through all elements except
    //first row and col and check for each
    //element if it lies in row or col
    //with zero
    for (ll i = 1; i < m; i++) {
        for (ll j = 1; j < n; j++) {
            if (A[i][0] == 0 || A[0][j] == 0)
                A[i][j] = 0;
        }
    }
    //if first col contains zero then
    //make all elements of that col as zero.
    if (row)
        for (ll i = 0; i < m; i++)
            A[i][0] = 0;

    //if first element of first row contains
    //zero then make all elements of first
    //row as zero.
    if (col)
        for (ll i = 0; i < n; i++)
            A[0][i] = 0;
}

void print(ll A[N][N], ll m, ll n)
{
    for (ll i = 0; i < m; i++) {
        for (ll j = 0; j < n; j++)
            cout << A[i][j] << " ";
        cout << "\n";
    }
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix: ";
        ll m, n;
        cin >> m >> n;

        cout << "Enter elements:\n";
        for (ll i = 0; i < m; i++)
            for (ll j = 0; j < n; j++)
                cin >> arr[i][j];

        //call solve function.
        solve(arr, m, n);

        //print final matrix.
        cout << "Final Matrix:\n";
        print(arr, m, n);
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter size of matrix: 3 3
Enter elements:
1 1 1
1 0 1
1 1 1
Final Matrix:
1 0 1 
0 0 0 
1 0 1 
Enter size of matrix: 2 2 
Enter elements:
1 2
3 4
Final Matrix:
1 2 
3 4 
Enter size of matrix: 3 3
Enter elements:
1 2 3 
4 5 6
7 0 8
Final Matrix:
1 0 3 
4 0 6 
0 0 0