Change all elements of row `i` and column `j` in a matrix to 0 if cell `(i, j)` is 0
Given an M × N matrix consisting of only 0 or 1, change all elements of row i and column j to 0 if cell (i, j) has value 0. Do this without using any extra space for every (i, j) having value 0.
For example,
Input:
[ 1 1 0 1 1 ]
[ 1 1 1 1 1 ]
[ 1 1 1 0 1 ]
[ 1 1 1 1 1 ]
[ 0 1 1 1 1 ]
Output:
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
Explanation:
0’s are present at (0, 2), (4, 0), and (2, 3) in the input matrix. So, we change all elements of the following cells to 0:
[ 1 1 0 1 1 ]
[ 1 1 1 1 1 ]
[ 1 1 1 0 1 ]
[ 1 1 1 1 1 ]
[ 0 1 1 1 1 ]
Output:
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
Explanation:
0’s are present at (0, 2), (4, 0), and (2, 3) in the input matrix. So, we change all elements of the following cells to 0:
- row 0 and column 2
- row 4 and column 0
- row 2 and column 3
A simple solution is to traverse the matrix and if we encounter any cell (i, j) that has value 0, change each element in the row i and column j to some arbitrary value other than 0 or 1. Later traverse the matrix once again and replace all elements with assigned value to 0.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <iostream> #include <vector> using namespace std; // Function to print the matrix void printMatrix(vector<vector<int>> const &mat) { for (auto &row: mat) { for (auto &i: row) { cout << i << " "; } cout << endl; } cout << endl; } // Function to change all elements of row `x` and column `y` to -1 void changeRowColumn(vector<vector<int>> &mat, int x, int y) { // `M × N` matrix int M = mat.size(); int N = mat[0].size(); for (int j = 0; j < N; j++) { if (mat[x][j] != 0) { mat[x][j] = -1; } } for (int i = 0; i < M; i++) { if (mat[i][y] != 0) { mat[i][y] = -1; } } } // Function to convert the matrix void convert(vector<vector<int>> &mat) { // base case if (mat.size() == 0) { return; } // `M × N` matrix int M = mat.size(); int N = mat[0].size(); // traverse the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i][j] == 0) // cell `(i, j)` has value 0 { // change each non-zero element in row `i` and column `j` to -1 changeRowColumn(mat, i, j); } } } // traverse the matrix once again and replace cells having // value -1 with 0 for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i][j] == -1) { mat[i][j] = 0; } } } } int main() { vector<vector<int>> mat = { { 1, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 }, { 0, 1, 1, 1, 1 } }; // convert the matrix convert(mat); // print matrix printMatrix(mat); return 0; } |
Output:
0 0 0 0 0
0 1 0 1 1
0 0 0 0 0
0 1 0 1 1
0 0 0 0 0
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
import java.util.Arrays; class Main { // Function to change all elements of row `x` and column `y` to -1 public static void changeRowColumn(int[][] mat, int M, int N, int x, int y) { for (int j = 0; j < N; j++) { if (mat[x][j] != 0) { mat[x][j] = -1; } } for (int i = 0; i < M; i++) { if (mat[i][y] != 0) { mat[i][y] = -1; } } } // Function to convert the matrix public static void convert(int[][] mat) { // base case if (mat == null || mat.length == 0) { return; } // `M × N` matrix int M = mat.length; int N = mat[0].length; // traverse the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i][j] == 0) // cell `(i, j)` has value 0 { // change each non-zero element in row `i` and column `j` to -1 changeRowColumn(mat, M, N, i, j); } } } // traverse the matrix once again and replace cells having // value -1 with 0 for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i][j] == -1) { mat[i][j] = 0; } } } } public static void main(String[] args) { int[][] mat = { { 1, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 }, { 0, 1, 1, 1, 1 } }; // convert the matrix convert(mat); // print matrix for (var r: mat) { System.out.println(Arrays.toString(r)); } } } |
Output:
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
# Function to change all elements of row `x` and column `y` to -1 def changeRowColumn(mat, M, N, x, y): for j in range(N): if mat[x][j]: mat[x][j] = -1 for i in range(M): if mat[i][y]: mat[i][y] = -1 # Function to convert the matrix def convert(mat): # base case if not mat or not len(mat): return # `M × N` matrix (M, N) = (len(mat), len(mat[0])) # traverse the matrix for i in range(M): for j in range(N): if mat[i][j] == 0: # cell `(i, j)` has value 0 # change each non-zero element in row `i` and column `j` to -1 changeRowColumn(mat, M, N, i, j) # traverse the matrix once again and replace cells having # value -1 with 0 for i in range(M): for j in range(N): if mat[i][j] == -1: mat[i][j] = 0 if __name__ == '__main__': mat = [ [1, 1, 0, 1, 1], [1, 1, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 1] ] # convert the matrix convert(mat) # print matrix for r in mat: print(r) |
Output:
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 0, 0, 0, 0]
The time complexity of the proposed solution is O(M × N × (M + N)), which is not efficient for an M × N matrix.
We can solve this problem in O(M × N) time as well. The idea is to traverse the matrix once and use the first row and the first column (or last row and last column) to mark if any cell in the corresponding row or column has a value 0 or not. Before doing that, initially mark if the chosen row/column has any 0's present in them in two different flags.
Following is the C++, Java, and Python implementation of the idea. Note that this method will work for any integer matrix (not just binary matrix).
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <iostream> #include <vector> using namespace std; // Function to print the matrix void printMatrix(vector<vector<int>> const &mat) { for (auto &row: mat) { for (auto &i: row) { cout << i << " "; } cout << endl; } cout << endl; } // Function to convert the matrix void convert(vector<vector<int>> &mat) { // base case if (mat.size() == 0) { return; } // `M × N` matrix int M = mat.size(); int N = mat[0].size(); bool rowFlag = false, colFlag = false; // scan the first row for any 0's for (int j = 0; j < N; j++) { if (!mat[0][j]) { rowFlag = true; break; } } // scan the first column for any 0's for (int i = 0; i < M; i++) { if (!mat[i][0]) { colFlag = true; break; } } // process the rest of the matrix and use the first row and the // first column to mark if any cell in the corresponding // row or column has a value 0 or not for (int i = 1; i < M; i++) { for (int j = 1; j < N; j++) { if (!mat[i][j]) { mat[0][j] = mat[i][0] = 0; } } } // if `(0, j)` or `(i, 0)` is 0, assign 0 to cell `(i, j)` for (int i = 1; i < M; i++) { for (int j = 1; j < N; j++) { if (!mat[0][j] || !mat[i][0]) { mat[i][j] = 0; } } } // if `rowFlag` is true, then assign 0 to all cells of the first row for (int i = 0; rowFlag && i < N; i++) { mat[0][i] = 0; } // if `colFlag` is true, then assign 0 to all cells of the first column for (int i = 0; colFlag && i < M; i++) { mat[i][0] = 0; } } int main() { vector<vector<int>> mat = { { 5, 3, 0, 8, 1 }, { 8, 1, 8, 4, 7 }, { 2, 6, 5, 0, 3 }, { 1, 4, 2, 7, 9 }, { 0, 1, 3, 6, 5 } }; // convert the matrix convert(mat); // print matrix printMatrix(mat); return 0; } |
Output:
0 0 0 0 0
0 1 0 0 7
0 0 0 0 0
0 4 0 0 9
0 0 0 0 0
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import java.util.Arrays; class Main { // Function to convert the matrix private static void convert(int[][] mat) { // base case if (mat == null || mat.length == 0) { return; } int M = mat.length; int N = mat[0].length; boolean rowFlag = false, colFlag = false; // scan the first row for any 0's for (int j = 0; j < N; j++) { if (mat[0][j] == 0) { rowFlag = true; break; } } // scan the first column for any 0's for (int i = 0; i < M; i++) { if (mat[i][0] == 0) { colFlag = true; break; } } // process the rest of the matrix and use the first row and the // first column to mark if any cell in the corresponding // row or column has a value 0 or not for (int i = 1; i < M; i++) { for (int j = 1; j < N; j++) { if (mat[i][j] == 0) { mat[0][j] = mat[i][0] = 0; } } } // if `(0, j)` or `(i, 0)` is 0, assign 0 to cell `(i, j)` for (int i = 1; i < M; i++) { for (int j = 1; j < N; j++) { if (mat[0][j] == 0 || mat[i][0] == 0) { mat[i][j] = 0; } } } // if `rowFlag` is true, then assign 0 to all cells of the first row for (int i = 0; rowFlag && i < N; i++) { mat[0][i] = 0; } // if `colFlag` is true, then assign 0 to all cells of the first column for (int i = 0; colFlag && i < M; i++) { mat[i][0] = 0; } } public static void main(String[] args) { int[][] mat = { { 5, 3, 0, 8, 1 }, { 8, 1, 8, 4, 7 }, { 2, 6, 5, 0, 3 }, { 1, 4, 2, 7, 9 }, { 0, 1, 3, 6, 5 } }; // convert the matrix convert(mat); // print matrix for (var r: mat) { System.out.println(Arrays.toString(r)); } } } |
Output:
[0, 0, 0, 0, 0]
[0, 1, 0, 0, 7]
[0, 0, 0, 0, 0]
[0, 4, 0, 0, 9]
[0, 0, 0, 0, 0]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
# Function to convert the matrix def convert(mat): # base case if not mat or not len(mat): return (M, N) = (len(mat), len(mat[0])) rowFlag = colFlag = False # scan the first row for any 0's for j in range(N): if mat[0][j] == 0: rowFlag = True break # scan the first column for any 0's for i in range(M): if mat[i][0] == 0: colFlag = True break # process the rest of the matrix and use the first row and the # first column to mark if any cell in the corresponding # row or column has a value 0 or not for i in range(1, M): for j in range(1, N): if mat[i][j] == 0: mat[0][j] = mat[i][0] = 0 # if `(0, j)` or `(i, 0)` is 0, assign 0 to cell `(i, j)` for i in range(1, M): for j in range(1, N): if mat[0][j] == 0 or mat[i][0] == 0: mat[i][j] = 0 # if `rowFlag` is true, then assign 0 to all cells of the first row i = 0 while rowFlag and i < N: mat[0][i] = 0 i = i + 1 # if `colFlag` is true, then assign 0 to all cells of the first column i = 0 while colFlag and i < M: mat[i][0] = 0 i = i + 1 if __name__ == '__main__': mat = [ [5, 3, 0, 8, 1], [8, 1, 8, 4, 7], [2, 6, 5, 0, 3], [1, 4, 2, 7, 9], [0, 1, 3, 6, 5] ] # convert the matrix convert(mat) for r in mat: print(r) |
Output:
[0, 0, 0, 0, 0]
[0, 1, 0, 0, 7]
[0, 0, 0, 0, 0]
[0, 4, 0, 0, 9]
[0, 0, 0, 0, 0]
Also See:
Find the index of a row containing the maximum number of 1’s in a binary matrix
Report all occurrences of an element in a row-wise and column-wise sorted matrix in linear time
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)