Set Matrix Zero

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

Example

Input: matrix = [[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]]

Approach

We will be using two extra arrays to solve the given problem

• First, we will declare two arrays: a row array of size N and a col array of size M and both are initialized with 0.
• Then, we will use two loops(nested loops) to traverse all the cells of the matrix.
• If any cell (i,j) contains the value 0, we will mark ith index of row array i.e. row[i] and jth index of col array col[j] as 1. It signifies that all the elements in the ith row and jth column will be 0 in the final matrix.
• We will perform step 3 for every cell containing 0.
• Finally, we will again traverse the entire matrix and we will put 0 into all the cells (i, j) for which either row[i] or col[j] is marked as 1.
• Thus we will get our final matrix.

We are marking the ith index of row array i.e. row[i], and jth index of col array i.e. col[j] with 1. These marked indices of the two arrays, row and col will tell us for which rows and columns we need to change the values to 0. For any cell (i, j), if the row[i] or col[j] is marked with 1, we will change the value of cell(i, j) to 0.

Complexity

• Time Complexity:  O(2*(N*M))
  • We are traversing the entire matrix 2 times and each traversal is taking O(N*M) time complexity.

• Space Complexity: O(N) + O(M)
  • O(N) is for using the row array and O(M) is for using the col array.

Code

#Java

import java.util.*;

public class MatrixZero {
    static ArrayList<ArrayList<Integer>> setMatrixZeros(ArrayList<ArrayList<Integer>> matrix, int numRows, int numCols) {
        int[] rowFlags = new int[numRows]; // Array to track zero-marked rows
        int[] colFlags = new int[numCols]; // Array to track zero-marked columns

        // Traverse the matrix:
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (matrix.get(i).get(j) == 0) {
                    // Mark the current row and column for zero
                    rowFlags[i] = 1;
                    colFlags[j] = 1;
                }
            }
        }

        // Set elements to zero based on marked rows and columns
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (rowFlags[i] == 1 || colFlags[j] == 1) {
                    matrix.get(i).set(j, 0);
                }
            }
        }

        return matrix;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();
        matrix.add(new ArrayList<>(Arrays.asList(0, 1, 2, 0)));
        matrix.add(new ArrayList<>(Arrays.asList(3, 4, 5, 2)));
        matrix.add(new ArrayList<>(Arrays.asList(1, 3, 1, 5)));

        int numRows = matrix.size();
        int numCols = matrix.get(0).size();

        ArrayList<ArrayList<Integer>> resultMatrix = setMatrixZeros(matrix, numRows, numCols);

        System.out.println("The Final matrix is: ");
        for (ArrayList<Integer> row : resultMatrix) {
            for (Integer element : row) {
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }
}

Output

The Final matrix is:
0 0 0 0 
0 4 5 0 
0 3 1 0