Given a Matrix arr of size M x N, the task is to set all rows and columns to zeroes if a particular element is zero, in constant space complexity.
Set Matrix Zeroes
Examples:
Input: [ [1, 1, 1],
[1, 0, 1],
[1, 1, 1]]
Output: [ [1, 0, 1],
[0, 0, 0],
[1, 0, 1]]
Explanation: one zero is present at cell(2,2), and all the elements in the 2nd row and 2nd column are marked as zeroes.Input: [[ 0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]]
Output: [[0, 0, 0, 0],
[0, 4, 5, 0],
[0, 3, 1, 0]]
Explanation: There are zeroes present in the 1st row at 1st column and 4th column.
Naive approach:
- First, we traverse the matrix using two nested loops.
- For each cell (i, j) if it is 0 then mark all the elements of row i and col j as -1 except that contains zero.
- Then traverse the matrix and mark cell 0 which contains -1.
- We get our final matrix.
Below is the Implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;void SetMatrixZeroes(vector<vector<int> >& arr){ // Traverse the matrix // using 2 nested loops for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { // If the cell contains zero // then mark its row // and column zero if (arr[i][j] == 0) { // Marking ith row // elements zero for (int c = 0; c < arr[i].size(); c++) { if (arr[i]) { arr[i] = -1; } } // Marking jth column // elements zero for (int r = 0; r < arr.size(); r++) { if (arr[r][j]) { arr[r][j] = -1; } } } } } for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { if (arr[i][j] == -1) arr[i][j] = 0; } }}// Driver codeint main(){ vector<vector<int> > arr = { { 0, 1, 2, 0 }, { 3, 4, 5, 2 }, { 1, 3, 1, 5 } }; // Function call SetMatrixZeroes(arr); for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { cout << arr[i][j] << " "; } cout << endl; } return 0;} |
Java
//Java code for the above approachimport java.util.Arrays;public class GFG { public static void setMatrixZeroes(int[][] matrix) { int rows = matrix.length; int cols = matrix[0].length; // Arrays to mark rows and columns to be zeroed boolean[] zeroRows = new boolean[rows]; boolean[] zeroCols = new boolean[cols]; // Traverse the matrix to mark rows and columns to be zeroed for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == 0) { zeroRows[i] = true; zeroCols[j] = true; } } } // Set elements to zero based on marked rows and columns for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (zeroRows[i] || zeroCols[j]) { matrix[i][j] = 0; } } } } public static void main(String[] args) { int[][] matrix = { {0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5} }; // Function call setMatrixZeroes(matrix); // Print the modified 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(); } }} |
Python3
def set_matrix_zeroes(matrix): rows, cols = len(matrix), len(matrix[0]) zero_rows, zero_cols = set(), set() # Identify rows and columns containing zeroes for i in range(rows): for j in range(cols): if matrix[i][j] == 0: zero_rows.add(i) zero_cols.add(j) # Set rows with zeroes to all zeroes for row in zero_rows: for j in range(cols): matrix[row][j] = 0 # Set columns with zeroes to all zeroes for col in zero_cols: for i in range(rows): matrix[i][col] = 0# Driver codeif __name__ == "__main__": matrix = [ [0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5] ] set_matrix_zeroes(matrix) for row in matrix: for num in row: print(num, end=" ") print() |
C#
using System;using System.Collections.Generic;class Program{ static void SetMatrixZeroes(List<List<int>> arr) { // Traverse the matrix using 2 nested loops for (int i = 0; i < arr.Count; i++) { for (int j = 0; j < arr[0].Count; j++) { // If the cell contains zero, mark its row and column as -1 if (arr[i][j] == 0) { // Marking ith row elements as -1 for (int c = 0; c < arr[i].Count; c++) { if (arr[i] != 0) { arr[i] = -1; } } // Marking jth column elements as -1 for (int r = 0; r < arr.Count; r++) { if (arr[r][j] != 0) { arr[r][j] = -1; } } } } } // Replace -1 with 0 in the matrix for (int i = 0; i < arr.Count; i++) { for (int j = 0; j < arr[0].Count; j++) { if (arr[i][j] == -1) { arr[i][j] = 0; } } } } static void Main() { List<List<int>> arr = new List<List<int>> { new List<int> {0, 1, 2, 0}, new List<int> {3, 4, 5, 2}, new List<int> {1, 3, 1, 5} }; // Function call SetMatrixZeroes(arr); for (int i = 0; i < arr.Count; i++) { for (int j = 0; j < arr[0].Count; j++) { Console.Write(arr[i][j] + " "); } Console.WriteLine(); } }} |
Output
0 0 0 0 0 4 5 0 0 3 1 0
Time Complexity: O((N*M)*(N + M)) + O(N*M), where N = no. of rows in the matrix and M = no. of columns in the matrix. we are traversing the matrix to find the cells with the value 0. It takes O(N*M).
Auxillary space: O(1) as we are not using any extra space.
Better Approach:
In the previous approach we have updated the row and column by -1 while traversing the matrix. So Idea here is Somehow we have to store which rows and columns are supposed to mark with zeroes.
Follow the steps to solve the problem:
- A row array of size N and a col array of size M are initialized with 0 to store which row and which column to mark with zeroes.
- Then, we will use two loops to traverse all the cells of the matrix.
- For each cell (i, j) containing the value 0, we will mark the ith index of the row array i.e. row[i], and jth index of col array col[j] as 1. It signifies that all the elements in the ith row and jth column will be 0 in the final matrix.
- Finally, we will again traverse the entire matrix and we will put 0 into all the cells (i, j) for which either row[i] or col[j] is marked as 1.
- Thus we will get our final matrix.
Below is the Implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;void SetMatrixZeroes(vector<vector<int> >& arr){ int n = arr.size(), m = arr[0].size(); // To store which rows and columns // are supposed to mark with zeroes. vector<int> row(n, 0), col(m, 0); // Traverse the matrix using // 2 nested loops for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { // If the cell contains zero // then mark its row // and column zero if (arr[i][j] == 0) { row[i] = 1; col[j] = 1; } } } for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { // Mark cells zero if any // of the row[i] or col[j] is 1 if (row[i] || col[j]) arr[i][j] = 0; } }}// Driver Codeint main(){ vector<vector<int> > arr = { { 0, 1, 2, 0 }, { 3, 4, 5, 2 }, { 1, 3, 1, 5 } }; // Function call SetMatrixZeroes(arr); for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { cout << arr[i][j] << " "; } cout << endl; } return 0;} |
Java
import java.util.Arrays;public class MatrixZeroes { static void setMatrixZeroes(int[][] arr) { int n = arr.length; int m = arr[0].length; // To store which rows and columns are supposed to mark with zeroes. int[] row = new int[n]; int[] col = new int[m]; // Traverse the matrix using 2 nested loops for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the cell contains zero, then mark its row and column zero if (arr[i][j] == 0) { row[i] = 1; col[j] = 1; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Mark cells zero if any of the row[i] or col[j] is 1 if (row[i] == 1 || col[j] == 1) arr[i][j] = 0; } } } public static void main(String[] args) { int[][] arr = { { 0, 1, 2, 0 }, { 3, 4, 5, 2 }, { 1, 3, 1, 5 } }; // Function call setMatrixZeroes(arr); // Print the modified matrix 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(); } }}//This code is contributed by chinmaya121221 |
Output
0 0 0 0 0 4 5 0 0 3 1 0
Time Complexity: O(2*(N*M)), where N = no. of rows in the matrix and M = no. of columns in the matrix.
Auxillary Space: O(N) + O(M), O(N) is for using the row array and O(M) is for using the col array.
Efficient Approach:
In the previous approach we had taken two arrays to store the ith row’s and jth column’s status, Idea here is to use the existing space i.e. matrix itself. We can use the first row and first column of a matrix to store which row elements and column elements to be marked as zeroes.
Follow the steps to solve the problem:
- First, we will traverse the matrix and update the first row and first column as follows we check for cell(i,j) if it is zero then we mark arr[i][0] equal to zero and arr[0][j] equal to zero.
- one special case to keep in mind is when i is 0, we will mark matrix[0][0] with 0 but if j is 0, we will mark the C0 variable with 0 instead of marking matrix[0][0] again because one cell can not represent for both row and column.
- Now we will traverse cells from (1,1) to (n-1,m-1) and update the matrix’s cell(i,j) according to the first row and first column.
- In the end, we will change the matrix’s first row and first column of the matrix as follows, we will change the row first and then the column.
- If arr[0][0] = 0, we will change all the elements from the cell (0,1) to (0, m-1), to 0.
- If C0 = 0, we will change all the elements from the cell (0,0) to (n-1, 0), to 0.
Below is the implementation of the above approach:
C++
// C++ code for the above aprpoach:#include <bits/stdc++.h>using namespace std;void SetarrZeroes(vector<vector<int> >& arr){ int n = arr.size(), m = arr[0].size(); int C0 = 1; // Traverse the arr and // mark 1st row & 1st // col as follows: for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] == 0) { // mark i-th row: arr[i][0] = 0; // mark j-th column: if (j == 0) C0 = 0; else arr[0][j] = 0; } } } // Mark with 0 from (1,1) // to (n-1, m-1): for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (arr[i][j] != 0) { // Check for col & row: if (arr[i][0] == 0 || arr[0][j] == 0) { arr[i][j] = 0; } } } } // Finally mark the // 1st row then 1st col: if (arr[0][0] == 0) { for (int j = 0; j < m; j++) { arr[0][j] = 0; } } if (C0 == 0) { for (int i = 0; i < n; i++) { arr[i][0] = 0; } }}// Driver Codeint main(){ vector<vector<int> > arr = { { 0, 1, 2, 0 }, { 3, 4, 5, 2 }, { 1, 3, 1, 5 } }; // Function call SetarrZeroes(arr); for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].size(); j++) { cout << arr[i][j] << " "; } cout << endl; } return 0;} |
Output
0 0 0 0 0 4 5 0 0 3 1 0
Time Complexity: O(2*(N*M))
Auxillary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
