Practice › Arrays
Set Matrix Zeroes
Medium · Arrays · Asked at Amazon, Microsoft, Adobe
If an element of the matrix is 0, set its entire row and column to 0. Print the resulting matrix.
Input
First line: r c. Next r lines: c integers each.
Output
The resulting matrix, r lines.
Constraints
- 1 ≤ r, c ≤ 200
Example 1
Input
3 3 1 1 1 1 0 1 1 1 1
Output
1 0 1 0 0 0 1 0 1
Example 2
Input
3 4 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
Hints
- Setting zeros while you scan would create new zeros that spread wrongly.
- First record which rows and which columns contain a 0, then clear them in a second pass.
Approach
Pass 1: mark zeroRow[i] and zeroCol[j] for every 0 found. Pass 2: an element becomes 0 if its row or its column is marked. Separating the passes stops zeros written in pass 2 from triggering more clearing. (For O(1) space, the first row and column can store these marks.)
Complexity: O(r·c) time · O(r + c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int r, c;
cin >> r >> c;
vector<vector<long long>> m(r, vector<long long>(c));
vector<bool> zr(r, false), zc(c, false);
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
cin >> m[i][j];
if (m[i][j] == 0) zr[i] = zc[j] = true;
}
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (zr[i] || zc[j]) m[i][j] = 0;
cout << m[i][j] << (j + 1 < c ? " " : "\n");
}
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
r, c = data[0], data[1]
m = [data[2 + i * c : 2 + (i + 1) * c] for i in range(r)]
zr = {i for i in range(r) if 0 in m[i]}
zc = {j for j in range(c) if any(m[i][j] == 0 for i in range(r))}
for i in range(r):
print(*(0 if i in zr or j in zc else m[i][j] for j in range(c)))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt(), c = sc.nextInt();
long[][] m = new long[r][c];
boolean[] zr = new boolean[r], zc = new boolean[c];
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
m[i][j] = sc.nextLong();
if (m[i][j] == 0) zr[i] = zc[j] = true;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
sb.append(zr[i] || zc[j] ? 0 : m[i][j]).append(j + 1 < c ? " " : "\n");
System.out.print(sb);
}
}