Unlock the complete
Logicmojo experience for FREE

1 Million +

Strong Tech Community

500 +

Questions to Practice

50 +

Jobs Referrals

Make Columns And Rows Zero

Back to home
Logicmojo - Updated Dec 12, 2023



Problem Statement: Make Columns And Rows Zero

Given a two-dimensional array, if any element within is zero, make its whole row and column zero. For example, consider the matrix below.



In the input matrix, at positions (0,0) and (0,3), there are two zeros. The result should be a matrix with zeros in the first row and zeros in the first and fourth columns.

One naive solution that comes to mind is to scan the 2D matrix and, if a zero is found, make the entire column and row zero. However, this is incorrect; even if there is only one zero in the matrix, the entire matrix will be zero.


Using Two Sets

We can record the row and column numbers of each cell in the matrix that has a zero. In the next cycle, all of the cells in this recorded row and column can be set to zero.

Algorithm

  1. 1. We make a pass over our original array and look for zero entries.

  2. 2. If we find that an entry at [i,j] is 0, we must record the row i and column j somewhere.

  3. 3. As a result, we use two sets: one for rows and one for columns.

  4. 4. Finally, we iterate over the original matrix.We examine each cell to see if the row r or column c has been marked previously. We set the value in the cell to 0 if any of them were marked.


Java Implementation:

class Solution {
  public void setZeroes(int[][] matrix) {
    int R = matrix.length;
    int C = matrix[0].length;
    Set<Integer> rows = new HashSet<Integer>();
    Set<Integer> cols = new HashSet<Integer>();

    // Essentially, we mark the rows and columns that are to be made zero
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (matrix[i][j] == 0) {
          rows.add(i);
          cols.add(j);
        }
      }
    }

    // Iterate over the array once again and using the rows and cols sets, update the elements.
    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (rows.contains(i) || cols.contains(j)) {
          matrix[i][j] = 0;
        }
      }
    }
  }
}


Python Implementation:

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        R = len(matrix)
        C = len(matrix[0])
        rows, cols = set(), set()

        # Essentially, we mark the rows and columns that are to be made zero
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        # Iterate over the array once again and using the rows and cols sets, update the elements
        for i in range(R):
            for j in range(C):
                if i in rows or j in cols:
                    matrix[i][j] = 0

Complexity Analysis

Time Complexity : O(M×N) where M and N are the number of rows and columns respectively.
Space Complexity : O(M + N).


With this article at Logicmojo, you must have the complete idea of solving Make Columns and Rows Zero problem.
© 2024 Logicmojo. ALL RIGHTS RESERVED