Set Matrix Zeroes

medium Matrix (2D arrays)

Problem

If a cell is 0, change its whole row and its whole column to 0. Print the new matrix. Zeros created by this rule must not cause more changes: only the zeros of the original matrix count.

Constraints

  • 1 <= r, c <= 200

Examples

Input

3 3
1 1 1
1 0 1
1 1 1

Output

1 0 1
0 0 0
1 0 1

Solutions

Best approachTime O(r * c)Space O(r + c)

Changing the matrix while scanning creates new zeros that look like original zeros, and the whole matrix becomes 0. Two marker arrays keep the original information safe. (An O(1) memory version stores the markers in the first row and column.)

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a matrix.
 * Input   : r and c, then r rows of c integers.
 * Output  : The new matrix.
 * Approach: Mark first, change later.
 * Time    : O(r * c)
 * Space   : O(r + c)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[][] m) {
        int rows = m.length;
        int cols = m[0].length;

        // Step 1: First find all rows and columns that must become zero. We must not change the matrix yet.
        boolean[] zeroRow = new boolean[rows];
        boolean[] zeroCol = new boolean[cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (m[i][j] == 0) {
                    zeroRow[i] = true;
                    zeroCol[j] = true;
                }
            }
        }

        // Step 2: Now build the output. A cell is 0 if its row or its column is marked.
        String[] output = new String[rows];
        for (int i = 0; i < rows; i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < cols; j++) {
                int value = zeroRow[i] || zeroCol[j] ? 0 : m[i][j];
                row.append(j == 0 ? "" : " ").append(value);
            }
            output[i] = row.toString();
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rows = scanner.nextInt();
        int cols = scanner.nextInt();
        int[][] m = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                m[i][j] = scanner.nextInt();
            }
        }
        System.out.println(String.join("\n", solve(m)));
    }
}
Hints (1)
  1. Why must we mark first and change later?