Set Matrix Zeroes In Place in DSA Java - Execution Trace

Concept Flow - Set Matrix Zeroes In Place

Start: Given matrix

↓

Scan matrix for zeros

↓

Mark rows and columns to zero

↓

Update matrix cells to zero based on marks

↓

Done: Matrix updated in place

We first scan the matrix to find zeros and mark their rows and columns. Then we update the matrix cells to zero in place based on these marks.

Execution Sample

DSA Java

int m = matrix.length;
int n = matrix[0].length;
boolean[] rows = new boolean[m];
boolean[] cols = new boolean[n];
// Mark rows and cols
for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) {
    if (matrix[i][j] == 0) {
      rows[i] = true;
      cols[j] = true;
    }
  }
}
// Set zeros
for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) {
    if (rows[i] || cols[j]) {
      matrix[i][j] = 0;
    }
  }
}

This code marks rows and columns that contain zero, then sets all cells in those rows and columns to zero.

Execution Table

Step	Operation	Matrix State	Rows Marked	Columns Marked	Pointer Changes	Visual State
1	Start with matrix	[[1,2,3],[4,0,6],[7,8,9]]	[]	[]	i=0,j=0	[1 2 3] [4 0 6] [7 8 9]
2	Check matrix[0][0]	[[1,2,3],[4,0,6],[7,8,9]]	[]	[]	i=0,j=0	[1 2 3] [4 0 6] [7 8 9]
3	Check matrix[0][1]	[[1,2,3],[4,0,6],[7,8,9]]	[]	[]	i=0,j=1	[1 2 3] [4 0 6] [7 8 9]
4	Check matrix[0][2]	[[1,2,3],[4,0,6],[7,8,9]]	[]	[]	i=0,j=2	[1 2 3] [4 0 6] [7 8 9]
5	Check matrix[1][0]	[[1,2,3],[4,0,6],[7,8,9]]	[]	[]	i=1,j=0	[1 2 3] [4 0 6] [7 8 9]
6	Check matrix[1][1] == 0, mark row 1 and col 1	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=1,j=1	[1 2 3] [4 0 6] [7 8 9]
7	Check matrix[1][2]	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=1,j=2	[1 2 3] [4 0 6] [7 8 9]
8	Check matrix[2][0]	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=2,j=0	[1 2 3] [4 0 6] [7 8 9]
9	Check matrix[2][1]	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=2,j=1	[1 2 3] [4 0 6] [7 8 9]
10	Check matrix[2][2]	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=2,j=2	[1 2 3] [4 0 6] [7 8 9]
11	Start setting zeros based on marks	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=0,j=0	[1 2 3] [4 0 6] [7 8 9]
12	matrix[0][0]: row0? no, col0? no → keep 1	[[1,2,3],[4,0,6],[7,8,9]]	[1]	[1]	i=0,j=0	[1 2 3] [4 0 6] [7 8 9]
13	matrix[0][1]: row0? no, col1? yes → set 0	[[1,0,3],[4,0,6],[7,8,9]]	[1]	[1]	i=0,j=1	[1 0 3] [4 0 6] [7 8 9]
14	matrix[0][2]: row0? no, col2? no → keep 3	[[1,0,3],[4,0,6],[7,8,9]]	[1]	[1]	i=0,j=2	[1 0 3] [4 0 6] [7 8 9]
15	matrix[1][0]: row1? yes → set 0	[[1,0,3],[0,0,6],[7,8,9]]	[1]	[1]	i=1,j=0	[1 0 3] [0 0 6] [7 8 9]
16	matrix[1][1]: row1? yes → set 0	[[1,0,3],[0,0,6],[7,8,9]]	[1]	[1]	i=1,j=1	[1 0 3] [0 0 6] [7 8 9]
17	matrix[1][2]: row1? yes → set 0	[[1,0,3],[0,0,0],[7,8,9]]	[1]	[1]	i=1,j=2	[1 0 3] [0 0 0] [7 8 9]
18	matrix[2][0]: row2? no, col0? no → keep 7	[[1,0,3],[0,0,0],[7,8,9]]	[1]	[1]	i=2,j=0	[1 0 3] [0 0 0] [7 8 9]
19	matrix[2][1]: row2? no, col1? yes → set 0	[[1,0,3],[0,0,0],[7,0,9]]	[1]	[1]	i=2,j=1	[1 0 3] [0 0 0] [7 0 9]
20	matrix[2][2]: row2? no, col2? no → keep 9	[[1,0,3],[0,0,0],[7,0,9]]	[1]	[1]	i=2,j=2	[1 0 3] [0 0 0] [7 0 9]
21	End of matrix update	[[1,0,3],[0,0,0],[7,0,9]]	[1]	[1]	Done	[1 0 3] [0 0 0] [7 0 9]

💡 All cells updated based on marked rows and columns

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 21
rows	[]	[false,true,false]	[false,true,false]	[false,true,false]
cols	[]	[false,true,false]	[false,true,false]	[false,true,false]
i	0	1	0	Done
j	0	1	0	Done
matrix	[[1,2,3],[4,0,6],[7,8,9]]	[[1,2,3],[4,0,6],[7,8,9]]	[[1,2,3],[4,0,6],[7,8,9]]	[[1,0,3],[0,0,0],[7,0,9]]

Key Moments - 3 Insights

Why do we mark rows and columns first instead of setting zeros immediately?

If we set zeros immediately, zeros created during update would affect other cells incorrectly. Marking first (see steps 1-10) ensures original zeros are tracked before changing the matrix.

Why do we need separate arrays for rows and columns?

We need to remember which rows and columns have zeros independently. This helps us update all cells in those rows and columns later (steps 11-21).

What happens if the matrix has no zeros?

No rows or columns get marked (rows and cols arrays stay false). So no cells change during update (steps 11-21). The matrix stays the same.

Visual Quiz - 3 Questions

Look at the execution table at step 6. Which row and column are marked?

A Row 2 and Column 2

B Row 0 and Column 0

C Row 1 and Column 1

D No rows or columns marked

💡 Hint

Check the 'Rows Marked' and 'Columns Marked' columns at step 6 in the execution table.

At which step does matrix[1][2] get set to zero?

A Step 17

B Step 15

C Step 13

D Step 19

💡 Hint

Look at the 'Operation' and 'Matrix State' columns in the execution table for when matrix[1][2] changes.

If matrix[2][0] was zero initially, how would the 'rows' array change after marking?

A rows[0] would be true

B rows[2] would be true

C rows[1] would be true

D No change in rows array

💡 Hint

Refer to the marking logic in steps 1-10 and how zeros mark their row.

Concept Snapshot

Set Matrix Zeroes In Place:
- Scan matrix to find zeros
- Mark rows and columns with zeros
- Update all cells in marked rows/columns to zero
- Do all changes in place without extra matrix
- Use boolean arrays to track rows and columns
- Avoid immediate zeroing to prevent cascading zeros

Full Transcript

We start with a matrix and scan each cell to find zeros. When a zero is found, we mark its entire row and column using two boolean arrays. After scanning, we update the matrix cells: if a cell is in a marked row or column, we set it to zero. This approach avoids changing the matrix while scanning, preventing incorrect zeroing. The process is done in place, modifying the original matrix without extra space for a copy. This method ensures all rows and columns containing zeros are correctly zeroed.

Practice

1. What is the main goal of the Set Matrix Zeroes In Place problem?

easy

A. Count the number of zero elements in the matrix.

B. Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space.

C. Sort each row of the matrix in ascending order.

D. Find the sum of all elements in the matrix.

Solution

1. Step 1: Understand the problem requirement

   The problem asks to set entire rows and columns to zero if any element in them is zero, modifying the matrix directly.

2. Step 2: Recognize the constraint of in-place modification

   We must do this without using extra space for another matrix or large data structures.

3. Final Answer:

   Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space. -> Option B

4. Quick Check:

   Goal = Set rows and columns to zero in-place [OK]

Hint: Remember: zero means zero entire row and column in-place [OK]

Common Mistakes:

• Using extra space like another matrix
• Only zeroing rows or columns, not both
• Not modifying the matrix in-place

2. Which of the following Java code snippets correctly declares a 2D integer matrix named matrix with 3 rows and 4 columns?

easy

A. int[][] matrix = new int[3][4];

B. int matrix[][] = new int[4][3];

C. int matrix[3][4];

D. int matrix = new int[3][4];

Solution

1. Step 1: Recall Java 2D array declaration syntax

   In Java, 2D arrays are declared as int[][] name = new int[rows][columns];.

2. Step 2: Match the correct dimensions

   int[][] matrix = new int[3][4]; uses 3 rows and 4 columns correctly. int matrix[][] = new int[4][3]; reverses dimensions, C is invalid syntax, D misses array brackets.

3. Final Answer:

   int[][] matrix = new int[3][4]; -> Option A

4. Quick Check:

   Java 2D array syntax = int[][] matrix = new int[3][4]; [OK]

Hint: Use int[][] for 2D arrays with new int[rows][cols] [OK]

Common Mistakes:

• Swapping rows and columns in new int[][]
• Using C-style array declaration
• Missing brackets in declaration

3. What will be the state of the matrix after running the following Java code snippet for setting matrix zeroes in place?

int[][] matrix = {
  {1, 2, 0},
  {4, 5, 6},
  {7, 0, 9}
};

// After applying setZeroes(matrix) method
// (method sets entire row and column to zero if element is zero)

medium

A. [[0, 0, 0], [4, 0, 0], [0, 0, 0]]

B. [[1, 0, 0], [4, 0, 0], [0, 0, 0]]

C. [[0, 0, 0], [4, 5, 0], [0, 0, 0]]

D. [[0, 2, 0], [4, 0, 6], [0, 0, 0]]

Solution

1. Step 1: Identify zero elements and their rows and columns

   Zeros are at positions (0,2) and (2,1). Rows 0 and 2, columns 1 and 2 must be zeroed.

2. Step 2: Set entire rows and columns to zero

   Row 0 becomes [0,0,0], row 2 becomes [0,0,0]. Column 1 and 2 in row 1 become 0, so row 1 becomes [4,0,0].

3. Final Answer:

   [[0, 0, 0], [4, 0, 0], [0, 0, 0]] -> Option A

4. Quick Check:

   Zero rows and columns set correctly = [[0, 0, 0], [4, 0, 0], [0, 0, 0]] [OK]

Hint: Mark zero rows and columns first, then update matrix [OK]

Common Mistakes:

• Only zeroing rows or columns, not both
• Not updating all affected cells
• Overwriting zeros too early

4. Consider this buggy Java code snippet for setting matrix zeroes in place:

public void setZeroes(int[][] matrix) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  boolean[] rowZero = new boolean[rows];
  boolean[] colZero = new boolean[cols];

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (matrix[i][j] == 0) {
        rowZero[i] = true;
        colZero[j] = true;
      }
    }
  }

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (rowZero[i] || colZero[j]) {
        matrix[i][j] = 0;
      }
    }
  }
}

What is the main issue with this code regarding the problem constraints?

medium

A. It modifies the matrix before checking all zeros, causing incorrect results.

B. It does not correctly identify zero elements in the matrix.

C. It causes an ArrayIndexOutOfBoundsException.

D. It uses extra space proportional to rows and columns, violating in-place requirement.

Solution

1. Step 1: Analyze space usage of the code

   The code uses two boolean arrays, rowZero and colZero, sized by rows and columns, which is extra space.

2. Step 2: Compare with problem constraints

   The problem requires in-place modification without extra space, so using these arrays violates the constraint.

3. Final Answer:

   It uses extra space proportional to rows and columns, violating in-place requirement. -> Option D

4. Quick Check:

   Extra space used = violates in-place [OK]

Hint: Avoid extra arrays; use matrix first row/column as markers [OK]

Common Mistakes:

• Ignoring space constraints
• Using extra arrays for marking
• Not handling first row/column carefully

5. You have a 4x4 matrix:

1 2 3 4
5 0 7 8
9 10 11 12
0 14 15 16

Using the in-place method for setting matrix zeroes, what will be the matrix after the operation?

hard

A. [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 15, 16]]

B. [[0, 0, 0, 4], [0, 0, 0, 0], [0, 0, 0, 12], [0, 0, 0, 0]]

C. [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]]

D. [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Solution

1. Step 1: Identify zero positions and mark rows and columns

   Zeros at (1,1) and (3,0). Rows 1 and 3, columns 0 and 1 must be zeroed.

2. Step 2: Set zeros for affected rows and columns

   Rows 1 and 3 become entirely zeros. Columns 0 and 1 become zeros across all rows, resulting in row 0: [0,0,3,4]; row 2: [0,0,11,12].

3. Final Answer:

   [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] -> Option C

4. Quick Check:

   Zero rows and columns updated correctly = [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] [OK]

Hint: Mark first row/column, then update matrix carefully [OK]

Common Mistakes:

• Zeroing entire rows or columns unnecessarily
• Missing zeros in some cells
• Not handling first row and column markers properly