Set Matrix Zeroes In Place in DSA Javascript

Mental Model

When a cell in a matrix is zero, set its entire row and column to zero without using extra space.

Analogy: Imagine a garden grid where if one plant dies (zero), the whole row and column of plants around it must be removed (set to zero) to prevent disease spread, but you only have a small notebook to mark which rows and columns to clear.

Matrix before:
1 2 3
4 0 6
7 8 9

We mark row 1 and column 1 to clear later.

Dry Run Walkthrough

Input: matrix: [[1,2,3],[4,0,6],[7,8,9]]

Goal: Set entire row and column to zero for each zero cell, modifying matrix in place without extra matrix.

Step 1: Check first row and first column for zeros to remember if they need zeroing later

Matrix unchanged:
1 2 3
4 0 6
7 8 9

Why: We need to know if first row or column should be zeroed at the end because we will use them as markers

Step 2: Traverse matrix from row 1 and col 1, mark zeros in first row and column

Mark matrix:
1 0 3
0 0 6
7 8 9

Why: Mark row 1 and column 1 because cell (1,1) is zero

Step 3: Use marks to set zeros in rows and columns except first row and column

Matrix after zeroing:
1 0 3
0 0 0
7 0 9

Why: Zero rows and columns based on marks to avoid extra space

Step 4: Zero first row if needed (no, because no original zero in first row)

Matrix unchanged:
1 0 3
0 0 0
7 0 9

Why: We only zero the first row if it originally contained a zero, tracked by firstRowZero flag

Step 5: Zero first column if needed (no, because no original zero in first column)

Final matrix:
1 0 3
0 0 0
7 0 9

Why: We only zero the first column if it originally contained a zero, tracked by firstColZero flag

Result:

1 0 3
0 0 0
7 0 9

Annotated Code

DSA Javascript

class Matrix {
  constructor(grid) {
    this.grid = grid;
  }

  setZeroes() {
    const matrix = this.grid;
    const rows = matrix.length;
    const cols = matrix[0].length;

    let firstRowZero = false;
    let firstColZero = false;

    // Check if first row has zero
    for (let c = 0; c < cols; c++) {
      if (matrix[0][c] === 0) {
        firstRowZero = true;
        break;
      }
    }

    // Check if first column has zero
    for (let r = 0; r < rows; r++) {
      if (matrix[r][0] === 0) {
        firstColZero = true;
        break;
      }
    }

    // Use first row and column as markers
    for (let r = 1; r < rows; r++) {
      for (let c = 1; c < cols; c++) {
        if (matrix[r][c] === 0) {
          matrix[r][0] = 0; // mark row
          matrix[0][c] = 0; // mark column
        }
      }
    }

    // Zero rows based on markers
    for (let r = 1; r < rows; r++) {
      if (matrix[r][0] === 0) {
        for (let c = 1; c < cols; c++) {
          matrix[r][c] = 0;
        }
      }
    }

    // Zero columns based on markers
    for (let c = 1; c < cols; c++) {
      if (matrix[0][c] === 0) {
        for (let r = 1; r < rows; r++) {
          matrix[r][c] = 0;
        }
      }
    }

    // Zero first row if needed
    if (firstRowZero) {
      for (let c = 0; c < cols; c++) {
        matrix[0][c] = 0;
      }
    }

    // Zero first column if needed
    if (firstColZero) {
      for (let r = 0; r < rows; r++) {
        matrix[r][0] = 0;
      }
    }
  }
}

// Driver code
const matrix = new Matrix([[1,2,3],[4,0,6],[7,8,9]]);
matrix.setZeroes();

// Print matrix
for (const row of matrix.grid) {
  console.log(row.join(' '));
}

for (let c = 0; c < cols; c++) { if (matrix[0][c] === 0) { firstRowZero = true; break; } }

Check if first row contains zero to know if it needs zeroing later

for (let r = 0; r < rows; r++) { if (matrix[r][0] === 0) { firstColZero = true; break; } }

Check if first column contains zero to know if it needs zeroing later

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

Mark rows and columns to be zeroed using first row and column

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

Zero entire rows based on marks

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

Zero entire columns based on marks

if (firstRowZero) { for (let c = 0; c < cols; c++) { matrix[0][c] = 0; } }

Zero first row if it originally contained zero

if (firstColZero) { for (let r = 0; r < rows; r++) { matrix[r][0] = 0; } }

Zero first column if it originally contained zero

Output

1 0 3

0 0 0

7 0 9

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each pass is linear in matrix size

Space: O(1) because we use the matrix itself for marking instead of extra memory

vs Alternative: Naive approach uses extra space O(m+n) to track rows and columns, this approach saves space by reusing matrix first row and column

Edge Cases

Matrix with no zeros

Matrix remains unchanged

DSA Javascript

if (matrix[r][c] === 0) { matrix[r][0] = 0; matrix[0][c] = 0; }

Matrix with zero in first row and first column

First row and column are zeroed at the end correctly

DSA Javascript

if (firstRowZero) { for (let c = 0; c < cols; c++) { matrix[0][c] = 0; } }

Single element matrix with zero

Single element set to zero, no errors

DSA Javascript

if (matrix[0][c] === 0) { firstRowZero = true; }

When to Use This Pattern

When asked to set entire rows and columns to zero based on zero cells without extra space, use the in-place marking pattern with first row and column as markers.

Common Mistakes

Mistake: Using extra arrays for rows and columns which increases space complexity
Fix: Use first row and column of the matrix itself as markers to achieve O(1) space

Mistake: Zeroing rows and columns immediately when zero is found, corrupting markers
Fix: First mark all rows and columns, then zero them in separate passes

Mistake: Not handling first row and first column separately causing incorrect zeroing
Fix: Check and store if first row or column originally had zeros before marking

Summary

Sets entire rows and columns to zero if any cell in them is zero, modifying matrix in place.

Use when you need to zero rows and columns without extra memory for tracking.

The key is to use the first row and column as markers to remember which rows and columns to zero.

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