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

#include <stdio.h>
#include <limits.h>

inline void clear(int m, int n, int a[][n], int row, int col)
{
    int k;

    for(k = 0; k < m; k++)
       if(a[k][col] != 0)
           a[k][col] = INT_MAX;

    for(k = 0; k < n; k++)
       if(a[row][k] != 0)
           a[row][k] = INT_MAX;

}

inline void print(const int m, const int n, int a[][n])
{
    int i, j;

    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
            printf("%d", a[i][j]);

        printf("\n");
    }
}

void setRowCol(const int m, const int n, int a[][n])
{
    int i = 0, j = 0, k;

    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            if(a[i][j] == 0)
            {
                clear(m, n, a, i, j);            }

    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            if(a[i][j] == INT_MAX)
            {
                a[i][j] = 0;
            }
}

int main()
{
    int a[][3] = { {2, 0, 4},
                  {1 ,2, 3},
                  {3, 5, 0},
                  {4, 5, 6}
                };

    setRowCol(4, 3, a);

    print(4, 3, a);
}
Advertisements

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

  1. The code doesn't work for the following input:{2, 0, 4}{1 ,2, 3}{3, 0, 5}{4, 5, 6}What we get is:0 0 01 0 33 0 54 0 6What we should get is:0 0 01 0 30 0 04 0 6We need to separate the logic for detecting zeros from the logic that sets rows & columns to zero .. instead of doing it in-place.

  2. There’s one problem with that solution though: we will “recognize” those 0s later on in our iteration and then set their row and column to zero Pretty soon, our entire matrix is 0s!
    One way around this is to keep a second matrix which flags the 0 locations We would then do a second pass through the matrix to set the zeros This would take O(MN) space

    class Matrix
    def initialize(input)
    @input = input
    @zeros = []
    end

    def solve
    @input.each_with_index do |row, i|
    row.each_with_index do |element, j|
    @zeros << [i,j] if element == 0
    end
    end

    @zeros.each do |x,y|
    set_h_zero(x)
    set_v_zero(y)
    end

    @input
    end

    private

    def set_h_zero(row)
    @input[row].map!{0}
    end

    def set_v_zero(col)
    @input.size.times do |r|
    @input[r][col] = 0
    end
    end
    end

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s