Set Matrix Zeroes In Place in DSA Javascript - 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

↓

Done: Matrix updated in place

We first scan the matrix to find zeros, mark which rows and columns to zero, then update the matrix in place.

Execution Sample

DSA Javascript

function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let rowZero = false;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
        if (i === 0) rowZero = true;
      }
    }
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }
  if (matrix[0][0] === 0) {
    for (let i = 0; i < m; i++) matrix[i][0] = 0;
  }
  if (rowZero) {
    for (let j = 0; j < n; j++) matrix[0][j] = 0;
  }
}

This code marks rows and columns to zero using the first row and column, then updates the matrix in place.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Initial matrix	[[1,1,1],[1,0,1],[1,1,1]]	rowZero=false	1 1 1 1 0 1 1 1 1
2	Find zero at (1,1), mark row 1 and col 1	[[1,0,1],[0,0,1],[1,1,1]]	matrix[1][0]=0, matrix[0][1]=0	1 0 1 0 0 1 1 1 1
3	No zero in first row, rowZero=false	[[1,0,1],[0,0,1],[1,1,1]]	rowZero=false	1 0 1 0 0 1 1 1 1
4	Update cells except first row/col	[[1,0,1],[0,0,0],[1,0,1]]	Set matrix[1][2]=0 (row 1 zero), matrix[2][1]=0 (col 1 zero)	1 0 1 0 0 0 1 0 1
5	Check first column zero at matrix[0][0]=1 (no)	[[1,0,1],[0,0,0],[1,0,1]]	No change	1 0 1 0 0 0 1 0 1
6	rowZero false, no change to first row	[[1,0,1],[0,0,0],[1,0,1]]	No change	1 0 1 0 0 0 1 0 1
7	End	[[1,0,1],[0,0,0],[1,0,1]]	Done	1 0 1 0 0 0 1 0 1

💡 All cells updated according to marked rows and columns, matrix set in place.

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
rowZero	false	false	false	false
matrix	[[1,1,1],[1,0,1],[1,1,1]]	[[1,0,1],[0,0,1],[1,1,1]]	[[1,0,1],[0,0,0],[1,0,1]]	[[1,0,1],[0,0,0],[1,0,1]]

Key Moments - 3 Insights

Why do we use the first row and first column to mark zeros instead of extra arrays?

Using the first row and column saves space by marking zeros in place, as shown in step 2 where matrix[1][0] and matrix[0][1] are set to zero to mark row and column.

Why do we need the rowZero variable?

Because the first row is used for marking columns, we need rowZero to remember if the first row itself should be zeroed, as explained in step 3 and step 6.

Why do we start updating from row 1 and column 1, not from 0?

Because the first row and column are used as markers, we update other cells first to avoid overwriting markers prematurely, as done in step 4.

Visual Quiz - 3 Questions

Look at the execution table at step 2, what cells are marked zero to indicate rows and columns to zero?

A matrix[1][0] and matrix[0][1]

B matrix[1][1] and matrix[0][0]

C matrix[0][0] and matrix[1][1]

D matrix[0][1] and matrix[1][2]

💡 Hint

Check the 'Pointer Changes' and 'Matrix State' columns at step 2 in the execution table.

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

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in the execution table for when cells are updated.

If the first row had a zero originally, which variable tracks that to zero out the first row later?

A matrix[0][0]

B rowZero

C matrix[0][1]

D matrix[1][0]

💡 Hint

Refer to the 'variable_tracker' and 'key_moments' about the role of rowZero.

Concept Snapshot

Set Matrix Zeroes In Place:
- Use first row and column as markers for zero rows/columns.
- Use a separate flag for first row zero.
- First pass: mark zeros.
- Second pass: update cells based on markers.
- Update first row and column last.
- Achieves O(1) extra space.

Full Transcript

We start with a matrix and want to set entire rows and columns to zero if any cell is zero. We scan the matrix to find zeros. Instead of extra arrays, we mark the first cell of the zero row and column as zero. We also track if the first row has zero with a flag. Then we update all cells except the first row and column based on these markers. Finally, we update the first row and column if needed. This method changes the matrix in place without extra space. The execution table shows each step, how the matrix changes, and pointer updates. Key moments clarify why we use the first row and column as markers and why we need the rowZero flag. The quiz tests understanding of marking and updating steps.

Practice

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

easy

A. Find the sum of all 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. Count how many zeroes are in the matrix.

D. Sort the matrix rows and columns after setting zeroes.

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 without extra space.

2. Step 2: Differentiate from other tasks

   Options B, C, and D describe different tasks like summing, counting, or sorting, which are not the goal here.

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 = Modify matrix in place [OK]

Hint: Focus on in-place zeroing of rows and columns [OK]

Common Mistakes:

• Thinking the problem is about counting zeroes
• Assuming extra space is allowed
• Confusing with sorting or summing tasks

2. Which of the following JavaScript code snippets correctly initializes a 3x3 matrix filled with zeros?

easy

A. const matrix = [[0,0,0],[0,0],[0,0,0]];

B. const matrix = Array(3).fill(Array(3).fill(0));

C. const matrix = Array.from({ length: 3 }, () => Array(3).fill(0));

D. const matrix = new Array(3).map(new Array(3).fill(0));

Solution

1. Step 1: Check each initialization method

   const matrix = Array(3).fill(Array(3).fill(0)); uses fill with the same inner array reference, causing all rows to point to the same array, which is incorrect.

2. Step 2: Identify correct independent row creation

   const matrix = Array.from({ length: 3 }, () => Array(3).fill(0)); uses Array.from with a function to create new arrays for each row, correctly initializing independent rows filled with zeros.

3. Final Answer:

   const matrix = Array.from({ length: 3 }, () => Array(3).fill(0)); -> Option C

4. Quick Check:

   Independent rows = const matrix = Array.from({ length: 3 }, () => Array(3).fill(0)); [OK]

Hint: Use Array.from with a function for independent rows [OK]

Common Mistakes:

• Using fill with array directly causing shared references
• Incorrect row lengths in nested arrays
• Using map on uninitialized arrays

3. What will be the matrix after running the following code?

function setZeroes(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  for (let i = 0; i < rows; i++) {
    if (matrix[i][0] === 0) firstColZero = true;
  }
  for (let j = 0; j < cols; j++) {
    if (matrix[0][j] === 0) firstRowZero = true;
  }

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }

  if (firstColZero) {
    for (let i = 0; i < rows; i++) matrix[i][0] = 0;
  }
  if (firstRowZero) {
    for (let j = 0; j < cols; j++) matrix[0][j] = 0;
  }
}

let mat = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
];
setZeroes(mat);
console.log(mat);

medium

A. [[1,0,1],[1,0,1],[1,0,1]]

B. [[0,0,0],[0,0,0],[0,0,0]]

C. [[1,1,1],[1,0,1],[1,1,1]]

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

Solution

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

   The zero is at position (1,1). The first row and column do not have zero initially. The code marks matrix[1][0] and matrix[0][1] as zero.

2. Step 2: Set zeroes based on marks and update first row/column if needed

   Using marks, the code sets matrix[1][1], matrix[1][2], matrix[0][1], and matrix[2][1] to zero. Since firstRowZero and firstColZero are false, no changes to first row or column.

3. Final Answer:

   [[1,0,1],[0,0,0],[1,0,1]] -> Option D

4. Quick Check:

   Zero at (1,1) zeroes row 1 and column 1 [OK]

Hint: Mark first row/col to track zero rows/columns [OK]

Common Mistakes:

• Not handling first row and column separately
• Overwriting marks too early
• Missing zeroing of entire row or column

4. The following code attempts to set matrix zeroes in place but has a bug. What is the bug?

function setZeroes(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (matrix[i][j] === 0) {
        for (let k = 0; k < cols; k++) matrix[i][k] = 0;
        for (let k = 0; k < rows; k++) matrix[k][j] = 0;
      }
    }
  }
}

medium

A. It modifies the matrix while iterating, causing incorrect zeroing.

B. It uses extra space which is not allowed.

C. It does not check for zero elements correctly.

D. It only sets zeroes in the first row and column.

Solution

1. Step 1: Analyze the nested loops and zero setting

   The code sets zeroes immediately when it finds a zero, modifying the matrix during iteration.

2. Step 2: Understand the effect of modifying during iteration

   Modifying the matrix while scanning causes new zeroes to appear, leading to extra rows and columns being zeroed incorrectly.

3. Final Answer:

   It modifies the matrix while iterating, causing incorrect zeroing. -> Option A

4. Quick Check:

   In-place modification during iteration causes errors [OK]

Hint: Avoid changing matrix while scanning for zeroes [OK]

Common Mistakes:

• Setting zeroes immediately instead of marking first
• Not separating scanning and updating phases
• Assuming immediate zeroing is safe

5. Given a 4x4 matrix:

[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5],
  [1,0,1,7]
]

After applying the in-place zeroing algorithm, what is the final matrix?

hard

A. [[0,0,0,0],[0,0,5,0],[0,0,1,0],[0,0,0,0]]

B. [[0,0,0,0],[3,4,5,2],[1,3,1,5],[1,0,1,7]]

C. [[0,1,2,0],[3,4,5,2],[1,3,1,5],[1,0,1,7]]

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

Solution

1. Step 1: Identify zero positions in the matrix

   Zeroes are at positions (0,0), (0,3), and (3,1). These mark rows 0 and 3, and columns 0, 1, and 3 for zeroing.

2. Step 2: Set entire rows and columns to zero based on marks

   Rows 0 and 3 become all zero. Columns 0, 1, and 3 become zero in all rows. The resulting matrix is [[0,0,0,0],[0,0,5,0],[0,0,1,0],[0,0,0,0]].

3. Final Answer:

   [[0,0,0,0],[0,0,5,0],[0,0,1,0],[0,0,0,0]] -> Option A

4. Quick Check:

   Zero rows and columns set correctly [OK]

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

Common Mistakes:

• Missing zeroing some columns or rows
• Overwriting matrix too early
• Not handling multiple zeroes correctly