The aim is to set all rows and columns to zeroes in a constant space complexity matrix of size M x N if a certain element is zero.
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.
Native method:
- Using two nested loops, we first iterate through the matrix, increasing its value by 1 and storing the maximum in k.
- After that, we will begin utilizing two loops to explore the matrix once more.
- Mark all of the elements in rows I and J as k, with the exception of those that contain zero, for each cell (i, j) if it is 0.
- Next, go through the matrix and mark cell 0 (containing k).
- Our final matrix is obtained.
- The application of the aforementioned strategy is seen below:
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
int k=INT_MIN;
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[0].size(); j++) {
if (arr[i][j] <k)
k=arr[i][j] ;
}
}
k=k+1;
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 as (max+1)
if (arr[i][j] == 0) {
// Marking ith row elements (max+1)
for (int c = 0; c < arr[i].size(); c++) {
if (arr[i][c]) {
arr[i][c] =k ;
}
}
// Marking jth column elements (max + 1)
for (int r = 0; r < arr.size(); r++) {
if (arr[r][j]) {
arr[r][j] = k;
}
}
}
}
}
//conveting all the elements which are marked as (max+1) to 0
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[0].size(); j++) {
if (arr[i][j] == k)
arr[i][j] = 0;
}
}
}
// Driver code
int 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 approach
import 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 code
if __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()JS
function setMatrixZeroes(matrix) {
// Variables to track rows and columns with zeroes
let zeroRows = new Set();
let zeroColumns = new Set();
// Traverse the matrix to find rows and columns with zeroes
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === 0) {
zeroRows.add(i);
zeroColumns.add(j);
}
}
}
// Set rows with zeroes to all zeroes
zeroRows.forEach(row => {
for (let j = 0; j < matrix[0].length; j++) {
matrix[row][j] = 0;
}
});
// Set columns with zeroes to all zeroes
zeroColumns.forEach(col => {
for (let i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
});
}
// Test the code
const arr = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
];
setMatrixZeroes(arr);
for (let i = 0; i < arr.length; i++) {
console.log(arr[i].join(' '));
}Output
0 0 0 0 0 4 5 0 0 3 1 0
Time Complexity: O((N*M)*(N + M)) + O(N*M),