Find solution
How to create a matrix?

Given a matrix with 1s and 0s, we need to create a matrix such that a [i] [j] =1, if only every element in ith row and jth column is 1, otherwise 0. We have to use constant space and have a optimal time complexity. What are some possible solutions?

  • We need to evaluate the original matrix and make a new matrix for the solution. Other then the solution matrix you can only use constant space for the solution.

  • Answer:

    This problem can be solved in O(N^2) and "constant" extra space if we are allowed to reuse the space in the solution matrix. First of all, check if the original matrix has at least one 0-element. If not, the solution matrix will consist of all 1s and we are done. So, let (i,j) be a 0-element. This means that row i and column j of the output matrix have to be filled with zeros eventually. So we can temporarily use that row and column as our scratchpad. Fill row i and column j of the output matrix with 1s. Go through all elements in the original matrix. For every 0-element (k,l), set elements (i,l) and (k,j) of the output matrix to 0 to signify that row k and column l of the output matrix need to be turned to zero eventually. Once this process is finished, we can fill the output matrix easily. For every (k,l) in the output matrix except for the ones with k=i and/or l=j, set it to 1 if both elements (i,l) and (k,j) are 1 and to 0 otherwise. After this, set all elements in row i and in column j to 0. It is easy to see that this algorithm takes only O(N^2) time and constant extra space (For loop counters and to store the identity of i and j).

Raziman T.V. at Quora Visit the source

Was this solution helpful to you?

Other answers

Here is a solution assuming you can edit the original matrix. Let mat(i,j) be the original matrix of size MxN. We will transform this into a sum matrix such that mat(i,j) contains sum of all elements in the rectangle from (0,0) to (i,j). The following code snippet will do that - for(int i = 0 ; i < M; i++){ for(int j = 0 ; j < N; j++){ mat[i][j] += ((i-1)>=0)?mat[i-1][j]:0; mat[i][j] += ((j-1)>=0)?mat[i][j-1]:0; mat[i][j] -= ((i-1)>=0 && (j-1)>=0)?mat[i-1][j-1]:0; } } Now we can calculate the sum of the ith row and jth column in the original matrix by subtracting the sum of 4 quadrants ( shaded in white in the fig) from the whole sum of the matrix.                                                                  Sum of upper left quadrant = mat(i-1, j-1) Sum of upper right quadrant = mat(i-1,N-1) - mat(i-1,j) Sum of lower left quadrant =  mat(M-1, j-1) - mat(i,j-1) Sum of right most quadrant  = mat(M-1, N-1) - mat(i,N-1) - m(M-1,j) - mat(i,j) Let the final matrix be trans(i,j). Set all elements of this matrix to 0. If the sum of ith row and jth column is M+N+1 then trans(i,j) = 1 else 0. Here is some code to do that - for(int i = 0 ; i < M; i++){ for(int j = 0 ; j < N; j++){ int sum = mat[M-1][N-1] - mat[i][N-1] - mat[M-1][j] + mat[i][j] ; if(i >=1){ sum += mat[i-1][N-1] - mat[i-1][j]; } if(j>=1){ sum += mat[M-1][j-1] - mat[i][j-1]; } if((i-1)>=0 && (j-1)>=0){ sum += mat[i-1][j-1]; } if( mat[M-1][N-1] - sum == (M+N+1)){ final[i][j] = 1; } } } This is O(n^2) since we only go over whole matrix twice and it's constant space.

Piyush Maheshwari

Here's my answer, if a[][] is the input matrix and c[][] is the output one: 1.Make c[i][0]=c[0][j] =1 for all i and j. 2.Now, go through each row, a[i][0...m-1]. If a[i][j]==0, set c[i][0]=0. Do the same for each column. 3.For all i,j: c[i][j]=c[i][0]&&c[0][j]. Only the first row and column should be filled in now. Filling the first row of c, in linear time. 1.Set c[0][0]=1. 2.Check a[0][0...m-1]. If a[0][j]=0, set c[0][0]=0. 3.Set c[0][j]=c[0][j]&&c[0][0]. Do the same for the first column.

Sri Aurobindo Munagala

One possible solution having time complexity O(n^2) and constant space complexity is as follows :-  // Program to create another matrix from a given matrix based on some criteria#include<iostream>#define ROWS 3#define COLUMNS 3int main(){ int nMat[ROWS][COLUMNS] = { {1, 1, 1}, {0, 1, 0}, {0, 1, 1} }; int nResMat[ROWS][COLUMNS]; for(int i = COLUMNS - 1; i > 0; i--) { nResMat[0][i] = 0; for(int j = 0; j < ROWS; j++) { nResMat[0][i] = nResMat[0][i] + nMat[j][i]; } if(nResMat[0][i] == ROWS) { nResMat[0][i] = 1; } else { nResMat[0][i] = 0; } } int nSumCol = 0; for(int j = 0; j < ROWS; j++) { nSumCol = nSumCol + nMat[j][0]; } if(nSumCol == ROWS) { nSumCol = 1; } else { nSumCol = 0; } for(int i = 0; i < ROWS; i++) { nResMat[i][0] = 0; for(int j = 0; j < COLUMNS; j++) { nResMat[i][0] = nResMat[i][0] + nMat[i][j]; } if(nResMat[i][0] == COLUMNS) { nResMat[i][0] = 1; } else { nResMat[i][0] = 0; } } for(int i = ROWS - 1; i >= 0; i--) { for(int j = COLUMNS - 1; j > 0; j--) { nResMat[i][j] = nResMat[i][0] * nResMat[0][j]; } } int nSumRow = nResMat[0][0]; nResMat[0][0] = nSumCol; for(int i = ROWS - 1; i > 0; i--) { nResMat[i][0] = nResMat[i][0] * nResMat[0][0]; } nResMat[0][0] = nSumRow * nSumCol; std::cout << "New matrix formed\n"; for(int i = 0; i < ROWS; i++) { for(int j = 0; j < COLUMNS; j++) { std::cout << nResMat[i][j] << " "; } std::cout << std::endl; } return 0;}

Sadik

just typing out the first thing that comes to mind int input[M][N], output[M][N];int i, j, k;for(i = 0;i < M; ++i){ int rowSum = 0, flag = 0; for(j = 0;j < N; ++j) { rowSum += input[i][j]; } flag = (rowSum == N) ? 1 : 0; for(j = 0;j < N; ++j) { output[i][j] = flag; }}for(j = 0;j < N; ++j){ int colSum = 0, flag = 0; for(i = 0;i < M; ++i) { colSum += input[i][j]; } flag = (colSum == M) ? 1 : 0; for(i = 0;i < M; ++i) { output[i][j] = (output[i][j] & flag); }}

Avinash Bhat

Related Q & A:

Just Added Q & A:

Find solution

For every problem there is a solution! Proved by Solucija.

  • Got an issue and looking for advice?

  • Ask Solucija to search every corner of the Web for help.

  • Get workable solutions and helpful tips in a moment.

Just ask Solucija about an issue you face and immediately get a list of ready solutions, answers and tips from other Internet users. We always provide the most suitable and complete answer to your question at the top, along with a few good alternatives below.