CareerCup

Assuming matrix is 0-based, i.e. the first element is at mat[0][0]

1. Use the first row and first column as table headers to contain row and column info respectively.
1.1 Note the element at mat[0][0]. If it is 1, it will require special handling at the end (described later)
2. Now, start scanning the inner matrix from index[1][1] up to the last element
2.1 If the element at[row][col] == 1 then update the table header data as follows
Row: mat[row][0] = 1;
Column: mat[0][col] = 1;
At this point we have the complete info on which column and row should be set to 1
3. Again start scanning the inner matrix starting from mat[1][1] and set each element
to 1 if either the current row or column contains 1 in the table header:
if ( (mat[row][0] == 1) || (mat[0][col] == 1) ) then set mat[row][col] to 1.

At this point we have processed all the cells in the inner matrix and we are
yet to process the table header itself
4. Process the table header
If the matt[0][0] == 1 then set all the elements in the first column and first
row to 1
5. Done

Time complexity O(2*((n-1)(m-1)+(n+m-1)), i.e. O(2*n*m - (n+m) + 1), i.e. O(2*n*m)
Space O(1)

And here is the link to my iplementation of the above algo:
codepad.org/fycIyflw

ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1315147537

1. use first as a bit map: bit 0 - there is 1's in column 0; bit 1 - there is 1's in row 0.
2. for each arr(i,j), where i,j > 0, if it is 1, set arr(0,j) and arr(i,0) to 1.
3. for each arr(i,j), where i,j > 0, if arr(0,j) or arr(i,0) is 1, set it to 1.
4. if bit 0 in first is 1, set all the elements in the column 0 to 1; if bit 1 in first 1, set all the elements in the row 0 to 1.
5. print out the 2d array.

O(2n*m) time and O(1) space

int[][] arr= new int[][] {{0,1,0,0}, {0,1,0,0}, {0,0,0,0}, {1,0,0,0}, {0,1,1,0}};
int first = 0;  
for (int i = 0; i<arr[0].length; i++) 
	if (arr[0][i] == 1) first |= 1; 
for (int i = 0; i<arr.length; i++) 
	if (arr[i][0] == 1) first |= 2;

for (int row = 1; row < arr.length; row++) {
	for (int col = 1; col < arr[0].length; col++) {
		if (arr[row][col]==1) {
			arr[0][col] = 1;
			arr[row][0] = 1;
		}
	}
}  

for (int i=1; i<arr.length; i++) {
	for (int j=1; j<arr[0].length; j++) {
		if (arr[0][j] == 1 || arr[i][0] == 1) arr[i][j] = 1;
	}
}
if ((first & 1) != 0) for (int i = 0; i<arr[0].length; i++) arr[0][i] = 1; 
if ((first & 2) != 0) for (int i = 1; i<arr.length; i++) arr[i][0] = 1;  

for (int i=0; i<arr.length; i++) {
	for (int j=0; j<arr[0].length; j++) {
		System.out.print(arr[i][j] + ",");
	}
	System.out.println();
}

Find out which are the intersections of zero rows and columns.

char[][] arr= new char[][] {{'1','1','0','1'}{ '0','0','0','0'}{ '0','0','0','1'}{ '0','0','0','1'}{ '0','1','1','0'}};
for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr[row].length; col++) {
if(arr[row][col]=='1')
{
for(int j=0;i<arr[row].length;j++)
if(a[row][j]=='0')
a[row][j]^=arr[row][col];
break;
} 
} }

int[][] arr= new int[][] {{1,1,0,1}{ 0,0,0,0}{ 0,0,0,1}{ 0,0,0,1}{ 0,1,1,0}};
for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr[row].length; col++) {
if(arr[row][col]==1)
{
for(int j=0;i<arr[row].length;j++)
if(a[row][j]==0)
a[row][j]^=arr[row][col];
break;
} 
} }

public static void updateMatrix(int a[][]) {
		int N = a.length;
		int M = a[0].length;

		//additional array space = N+M
		int a1[] = new int[N];// N
		int b1[] = new int[M];// M
		
		
		int i = 0, j = 0;
		//We store the 'OR' of rows in a1 and 'OR' of coulmns in b1
		for (i = 0; i < N; ++i)
			for (j = 0; j < M; ++j) {
				a1[i] |= a[i][j];
				b1[j] |= a[i][j];
			}
		//update the original array with a1|b1
		for (i = 0; i < N; ++i)
			for (j = 0; j < M; ++j) {
				a[i][j] = a1[i] | b1[j];
			}
	}

Use bitset class in c++. This will save the space too.

two way solving would if we forget the condition right now would be
1) take a bit array of o(n) as soon. start traversing row-wise. As soon as u get a 1 make all elements of row as 1. and also make bit_arr[i]=1. After row 1 check for the current element and bit_array[i] for 1. So complexity o(n*m) space complexity o(n)

2) second way is trivial solution in to traverse the matrix and each time find a 1 go to all the elements in the row and column and make them 1. Hell complexity

stackoverflow.com/questions/10840044/microsoft-interview-transforming-a-matrix

I guess this only needs O(nm) time and no extra space. Isn't it obvious this has to be the element which falls on the intersection of an all zero row and an all zero column?

If you want explanation: What exactly is happening in this situation if a position i,j has a 1 then the ith row and the jth column is transformed to all 1s.

So which element will be untouched? The one which lies in the all zero rows and all zero columns. Hence the one at the intersection.

1. Take the dot product of each row by itself and take its minimum with 1, this way we obtain 1 or 0 and we can make up bit by bit an unsigned integer (call it RowElements)

2. Repeat the same with columns (call it ColElements). In this way the storage requirement is 2 integers.

3. Now we set all entries in the matrix to be 1 except those where RowElements bit =0 and ColElements bit =0

Why: A*A'=0 only if we have a row of zeroes and A'*A=0 only for a column of zeroes. (transpose is A')

( we do not need actually dot product but the solution can be justified nicely this way, we can just get the bits together in one integer and if it is nonzero the corresponding bit in the auxiliary integer is set to 1, and if it is 0 then it is set to 0).

use of first row and column in matrix to remember whether this row/col should be marked all ones'

void fill_matrix_row_col(int **m, int h, int w){
	if(!m || !h || !w) return;
	bool rowones=false, colones=false;
	for(int i=0;i<h;++i)
		if(m[i][0]){
			colones=true;
			break;
		}
	for(int j=0;j<w;++j)
		if(m[0][j]){
			rowones=true;
			break;
		}
	for(int i=1;i<h;++i){
		for(int j=1;j<w;++j){
			if(m[i][j]) m[0][j]=m[i][0]=1;
		}
	}
	for(int i=1;i<h;++i){
		for(int j=1;j<w;++j)
			if(m[i][0] || m[0][j]) m[i][j]=1;
	}
	for(int i=0;i<h;++i)
		if(colones)
			m[i][0]=1;
		else
			m[i][0]=0;
	for(int j=0;j<w;++j)
		if(rowones)
			m[0][j]=1;
		else
			m[0][j]=0;

}

package com.careercup.book.four.one;

public class MatrixTransformer {

    private int[][] a;
    private int m;
    private int n;

    public MatrixTransformer(int[][] _a, int _m, int _n) {
        a = _a;
        m = _m;
        n = _n;
    }

    private int scanRow(int i) {
        int allZero = 0;
        for (int k = 0; k < n; k++)
            if (a[i][k] == 1) {
                allZero = 1;
                break;
            }

        return allZero;
    }

    private int scanColumn(int j) {
        int allZero = 0;
        for (int k = 0; k < m; k++)
            if (a[k][j] == 1) {
                allZero = 1;
                break;
            }

        return allZero;
    }

    private void setRowToAllOnes(int i) {
        for (int k = 0; k < n; k++)
            a[i][k] = 1;
    }

    private void setColToAllOnes(int j) {
        for (int k = 0; k < m; k++)
            a[k][j] = 1;
    }

    // # we're going to use the first row and column
    // # of the matrix to store row and column scan values,
    // # but we need aux storage to deal with the overlap
    // firstRow = scanRow(0)
    // firstCol = scanCol(0)
    //
    // # scan each column and store result in 1st row - O(mn) work

    public void transform() {
        int firstRow = scanRow(0);
        int firstCol = scanColumn(0);

        for (int k = 0; k < n; k++) {
            a[0][k] = scanColumn(k);
        }

        // now row 0 tells us whether each column is all zeroes or not
        // it's also the correct output unless row 0 contained a 1 originally

        for (int k = 0; k < m; k++) {
            a[k][0] = scanRow(k);
        }

        a[0][0] = firstCol | firstRow;

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                a[i][j] = a[0][j] | a[i][0];

        if (firstRow == 1) {
            setRowToAllOnes(0);
        }

        if (firstCol == 1)
            setColToAllOnes(0);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(a[i][j] + ", ");
            }
            sb.append("\n");
        }

        return sb.toString();
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] a = { { 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0 }, { 1, 0, 1, 1, 0 } };
        MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
        mt.transform();
        System.out.println(mt);
    }

}

Source: stackoverflow.com/questions/10840044/microsoft-interview-transforming-a-matrix

for(i=0;i<row;i++)
for(j=0;j<coloum;j++)
if (A[i][j] = =1)
row_col_fill(A,i,j,row,coloum);

for(i=0;i<row;i++)
for(j=0;j<coloum;j++)
if (A[i][j] = =2)
A[i][j] = 1;


void row_col_fill( int *A , int i,intj,int row,int coloum)
{
for(o=0;o<coloum;o++)
A[i][o] = 2;
for(o=0;o<row;o++)
A[o][j] = 2;
}

i guess the solution given by dharmendra is perfect :
there is no point pasting code .. just explain your algorithm , others can easily code your algorithm ..

I guess this only needs O(nm) time and no extra space. Isn't it obvious this has to be the element which falls on the intersection of an all zero row and an all zero column?

If you want explanation: What exactly is happening in this situation if a position i,j has a 1 then the ith row and the jth column is transformed to all 1s.

So which element will be untouched? The one which lies in the all zero rows and all zero columns. Hence the one at the intersection.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TransformMatrix
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] A = new int[,] { { 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0 }, {1, 0, 1, 1, 0} };
            Console.WriteLine("Original Matrix:");
            DisplayMatrix(A);
            TransFormMatrix(A);
            Console.WriteLine("\n\nTransformed Matrix:");
            DisplayMatrix(A);
            Console.ReadKey();
        }

        static void DisplayMatrix(int[,] A)        
        {
            int rows = A.GetLength(0);
            int cols = A.GetLength(1);

            for (int i = 0; i < rows; i++)
            {
                Console.WriteLine("\n");
                for (int j = 0; j < cols; j++)
                {
                    Console.Write("\t{0}",A[i,j]);
                }
            }
        }

        static void TransFormMatrix(int[,] A)
        {
            int rows = A.GetLength(0);
            int cols = A.GetLength(1);
            int firstRow = 0;
            int firstCol = 0;

            for (int i = 1; i < rows; i++)
            {
                for (int j = 1; j < cols; j++)
                {
                    if (A[i, j] == 1)
                    {
                        if (A[0, j] == 1) firstRow = 1;
                        A[0, j] = 1;
                        if (A[i, 0] == 1) firstCol = 1;
                        A[i, 0] = 1;
                    }
                }
            }


            for (int i = 1; i < rows; i++)
            {
                if (A[i, 0] == 1)
                {
                    for (int j = 1; j < cols; j++)
                    {
                        A[i, j] = 1;
                    }
                }
            }

            for (int j = 1; j < cols; j++)
            {
                if (A[0, j] == 1)
                {
                    for (int i = 1; i < rows; i++)
                    {
                        A[i, j] = 1;
                    }
                }
            }

            if (A[0, 0] == 1)
            {
                for (int i = 0; i < rows; i++)
                {
                    A[i, 0] = 1;
                }

                for (int j = 0; j < cols; j++)
                {
                    A[0, j] = 1;
                }
            }
            else
            {
                if (firstRow == 1)
                {
                    for (int i = 0; i < rows; i++)
                    {
                        A[i, 0] = 1;
                    }
                }
                if (firstCol == 1)
                {
                    for (int j = 0; j < cols; j++)
                    {
                        A[0, j] = 1;
                    }
                }
            }

        }
    }
}

Assume n,m<=32, my solution use bitmap:
Firstly we need to scan the the matrix and record down which rows and cols need to be set. Then for the second scanning we set the element according to the record done before.

int N, int M;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j] == 1) {
N = N | (0x01 << i);
M = M | (0x01 << j);
}
}
}

for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if((N & (0x01 << i)) || (M & (0x01 << j)))
a[i][j] = 1;
}
}

The idea is traversing the matrix twice.
The first one starts from cell [0][0] and ends at [n-1][m-1]
The next one is just the opposite order.

If you are going down and if a[i][j] is 1, then set these to 1:
a[i][j+1] and a[i+1][j]

If you are going up and if a[i][j] is 1, then set these to 1:
a[i][j-1] and a[i-1][j]

public class MatrixZeroColumnRows {

public static void main(String[] args) {

int[][] matrix = { { 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, }, { 0, 1, 0, 0, 0, }, { 1, 0, 1, 1, 0, } };

printMatrix(matrix);

int[] result = zeroIntersection(matrix);

System.out.println(" row number : " + result[0]);
System.out.println("Column number : " + result[1]);

}

public static void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(" " + matrix[i][j] + " ");

}
System.out.println();
}

}

public static int[] zeroIntersection(int[][] matrix) {
int[] arr = new int[2];
int row = 0;
int column = 0;

for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] != 0) {
break;
} else {
row++;
}
}
if (row == matrix[0].length) {
arr[0] = i;

}
row = 0;

}

for (int j = 0; j < matrix[0].length; j++) {
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][j] != 0) {
break;
} else {
column++;
}
}
if (column == matrix.length) {
arr[1] = j;

}
column = 0;

}

return arr;
}

}

Now once you get the row and column number , fill the matrix with 1 except matrix[1][4] =0 ;