Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Setting zeros while you scan would create new zeros that spread wrongly.
  2. 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);
    }
}

Solve Set Matrix Zeroes online · All practice problems