# Unlock the complete

Logicmojo experience for FREE

Sign Up Using

### 1 Million +

Strong Tech Community

### 500 +

Questions to Practice

### 50 +

Jobs Referrals

Logicmojo experience for FREE

Sign Up Using

Strong Tech Community

Questions to Practice

Jobs Referrals

- Problem Statement: Make Columns And Rows Zero
- Naive Approach
- Using Two Set

Logicmojo - Updated Dec 12, 2023

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.

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.

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

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

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

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.

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; } } } } }

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

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

**Space Complexity** : O(M + N).