You are given an N x M integer matrix. Your task is to modify this matrix in place so that if any cell contains the value 0, then all cells in the same row and column as that cell should also be set to 0.
Requirements:
You must do it in place.
For Example:
If the given grid is this:
[7, 19, 3]
[4, 21, 0]
Then the modified grid will be:
[7, 19, 0]
[0, 0, 0]
Input Format:
The first line of the input contains a single integer ‘T’ representing the no. of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the no. of the rows and columns of the matrix.
The next 'N' lines will contain ‘M’ space separated integers representing the elements of the matrix.
Output Format:
For each test case, print the modified grid.
Print output of each test case in a separate line.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints:
1 ≤ T ≤ 1000
1 ≤ m, n ≤ 1000
Σ(m * n) ≤ 2000000
-2^(31) ≤ matrix[i][j] ≤ 2^(31)-1, for all (1 ≤ i ≤ n and 1 ≤ j ≤ m).
Time Limit: 1 sec
Follow up:
Can we do better than O(m * n) space?
Using O(m + n) space is an improvement but we can still do better.
We can do it using constant memory. Can you do it?
2
2 3
7 19 3
4 21 0
3 3
1 2 3
4 0 6
7 8 9
7 19 0
0 0 0
1 0 3
0 0 0
7 0 9
For First Case - Similar to the example explained above.
For Second Case -
Only the cell (2,2) has zero. So all the elements of the second row and second column are changed to zeros.
2
4 2
1 0
2 7
3 0
4 8
3 3
0 2 3
1 0 3
1 2 0
0 0
2 0
0 0
4 0
0 0 0
0 0 0
0 0 0
We can simulate the process described in the statement naively.
The basic idea is to maintain another boolean matrix ‘isZero’ which stores whether our resultant matrix should contain a zero at a particular index or not. We can traverse every element of our original matrix. If the element is 0, then we traverse the complete row and complete column of that particular element and set isZero values accordingly to true for all the elements in that row and column.
Algorithm:
setZeros(matrix)
O(N * M * (M + N)) where N & M are dimensions of the given matrix.
We are traversing each element. For each element that is zero, we are traversing its complete row and column. So we have O(M * N) elements and for each element, we can traverse a row and a column in the worst case, i.e. O(M + N). So total complexity is O(M * N * (M + N).
O(N * M) where N & M are dimensions of the given matrix.
We need to declare a 2D boolean matrix of size n x m. So the total required space will be O(N * M).
All tags
Sort by
Interview problems
easy c++ solution
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
vector<vector<int>>ans=matrix;
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(matrix[i][j]==0)
{
int row=i;
int col=j;
for(int j=0;j<matrix[0].size();j++)
{
ans[row][j]=0;
}
for(int i=0;i<matrix.size();i++)
{
ans[i][col]=0;
}
}
}
}
matrix=ans;
}
Interview problems
JAVA BEST SOLUTION
import java.io.*;
import java.util.* ;
public class Solution {
public static void setZeros(int matrix[][]) {
int n = matrix.length;
int m = matrix[0].length;
int col[] =new int[m];
int row[] =new int[n];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j] ==0){
col[j] =1;
row[i] =1;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(row[i] == 1 || col[j] == 1){
matrix[i][j] =0;
}
}
}
}
}
Interview problems
Easy c++ solution
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
vector<pair<int,int>>p;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
if(matrix[i][j]==0){
p.push_back({i,j});
}
}
}
int i=0;
while(i<p.size()){
for(int j=0;j<matrix.size();j++){
matrix[j][p[i].second]=0;
}
for(int j=0;j<matrix[0].size();j++){
matrix[p[i].first][j]=0;
}
i++;
}
return ;
}
Interview problems
Java Easy Solution for "Set Matrix Zeros"
import java.io.*;
import java.util.* ;
public class Solution {
public static void setZeros(int matrix[][]) {
// Write your code here..
int n = matrix.length;
int m = matrix[0].length;
int col[] =new int[m];
int row[] =new int[n];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j] ==0){
col[j] =1;
row[i] =1;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(row[i] == 1 || col[j] == 1){
matrix[i][j] =0;
}
}
}
}
}
Interview problems
most easiest understandable solution in c++.with time complexity O(row*col)
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
vector<pair<int,int>>p;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
if(matrix[i][j]==0){
p.push_back({i,j});
}
}
}
int i=0;
while(i<p.size()){
for(int j=0;j<matrix.size();j++){
matrix[j][p[i].second]=0;
}
for(int j=0;j<matrix[0].size();j++){
matrix[p[i].first][j]=0;
}
i++;
}
return ;
}
Interview problems
using Python
from math import *
from collections import *
from sys import *
from typing import List
def setZeros(matrix):
# Write your code here.
n=len(matrix)
m=len(matrix[0])
zero_rows=set()
zer_columns=set()
for i in range(n):
for j in range(m):
if matrix[i][j]==0:
zero_rows.add(i)
zer_columns.add(j)
for i in range(n):
for j in range(m):
if i in zero_rows or j in zer_columns:
matrix[i][j]=0
return matrix
Interview problems
Brute Force Approach in C++
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
// Write your code here.
set<int> columns,rows;
int column = matrix[0].size();
int row = matrix.size();
for (int i = 0; i < row;i++) {
for (int j = 0; j < column;j++) {
if (matrix[i][j] == 0) {
rows.insert(i);
columns.insert(j);
}
}
}
vector <int> temp(column,0);
for (int i = 0; i < row;i++) {
if (rows.find(i) != rows.end()) {
matrix[i] = temp;
continue;
}
for (int j= 0; j < column;j++) {
if (columns.find(j) != columns.end()) {
matrix[i][j] = 0;
}
}
}
}
Interview problems
BRUTE FORCE C++ 🚀
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
// Write your code here.
vector<int> row(matrix.size(),0);
vector<int> column(matrix[0].size(),0);
int n=matrix.size();
int m=matrix[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(matrix[i][j]==0)
{
row[i]=1;
column[j]=1;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(row[i]==1 || column[j]==1)
{
matrix[i][j]=0;
}
}
}
}
Interview problems
Python- simple logic implementation
from math import *
from collections import *
from sys import *
from os import *
from typing import List
def setZeros(matrix: List[List[int]]) -> None:
coordinates = []
m, n = len(matrix), len(matrix[0])
# find and store all the 0's coordinates...
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
coordinates.append([i, j])
# use the co-ordintes information and set the entire row and col to zero..
for points in coordinates:
i, j = points
for k in range(0, m):
matrix[k][j] = 0
for l in range(0, n):
matrix[i][l] = 0
return matrix
Interview problems
Easy Solution in C++; please upvote
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
// Write your code here.
int n = matrix.size();
int m = matrix[0].size();
vector<int> row(n, 0);
vector<int> col(m, 0);
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(matrix[i][j] == 0) {
row[i] = 1;
col[j] = 1;
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(row[i] or col[j]) {
matrix[i][j] = 0;
}
}
}
}
