Set Matrix Zeroes In Place in DSA Typescript

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 grid of lights where if one light goes off, the whole row and column of lights must also go off, but you only have a small notebook to mark which rows and columns to turn off later.

Matrix before:
1 1 1
1 0 1
1 1 1

We mark the row and column of zero cells using the first row and first column as markers.

Dry Run Walkthrough

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

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

Step 1: Check first row and first column for zeros; mark if they contain zero

First row: [1,1,1], First column: [1,1,1]

Why: We need to know if first row or column should be zeroed later

Step 2: Traverse matrix from row 1, col 1; find zero at (1,1); mark first row and column

Matrix after marking:
1 0 1
0 0 1
1 1 1

Why: Marking first row and column to remember which rows and columns to zero

Step 3: Zero rows based on first column markers (row 1 marked)

Matrix after zeroing row 1:
1 0 1
0 0 0
1 1 1

Why: Row 1 must be zeroed because first column at row 1 is zero

Step 4: Zero columns based on first row markers (column 1 marked)

Matrix after zeroing column 1:
1 0 1
0 0 0
1 0 1

Why: Column 1 must be zeroed because first row at column 1 is zero

Step 5: Check if first row needs zeroing (no zero found initially)

Matrix unchanged:
1 0 1
0 0 0
1 0 1

Why: First row was not marked for zeroing

Step 6: Check if first column needs zeroing (no zero found initially)

Matrix unchanged:
1 0 1
0 0 0
1 0 1

Why: First column was not marked for zeroing

Result:

Final matrix:
1 0 1
0 0 0
1 0 1

Annotated Code

DSA Typescript

class MatrixZeroSetter {
  static setZeroes(matrix: number[][]): void {
    const rows = matrix.length;
    const cols = matrix[0].length;

    let firstRowHasZero = false;
    let firstColHasZero = false;

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

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

    // Use first row and column to mark zeros
    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 marks
    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 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 first row if needed
    if (firstRowHasZero) {
      for (let c = 0; c < cols; c++) {
        matrix[0][c] = 0;
      }
    }

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

// Driver code
const matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
];

MatrixZeroSetter.setZeroes(matrix);

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

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

Check if first row contains zero to handle it later

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

Check if first column contains zero to handle it 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 (firstRowHasZero) { for (let c = 0; c < cols; c++) { matrix[0][c] = 0; } }

Zero first row if it originally contained zero

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

Zero first column if it originally contained zero

Output

1 0 1

0 0 0

1 0 1

Complexity Analysis

Time: O(m*n) because we scan the entire matrix multiple times but each cell is visited a constant number of times

Space: O(1) because we use the matrix itself for marking without extra storage

vs Alternative: Naive approach uses extra space O(m+n) for row and column markers; this approach saves space by using first row and column as markers

Edge Cases

Matrix with no zeros

Matrix remains unchanged

DSA Typescript

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

Matrix where first row or first column contains zero

First row or column is zeroed at the end using flags

DSA Typescript

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

Matrix with multiple zeros in different rows and columns

All corresponding rows and columns are zeroed correctly

DSA Typescript

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

When to Use This Pattern

When you need to modify a matrix in place based on zero cells affecting entire rows and columns, use the first row and column as markers to save space.

Common Mistakes

Mistake: Zeroing rows and columns immediately when a zero is found, corrupting the matrix before marking all zeros
Fix: First mark all rows and columns to be zeroed using the first row and column, then zero them in a separate pass

Mistake: Not handling the first row and first column separately, causing incorrect zeroing
Fix: Use separate flags to track if first row or first column originally had zeros and zero them at the end

Summary

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

Use when you must zero rows and columns without extra space beyond the matrix itself.

Use the first row and column as markers to remember which rows and columns to zero later.

Practice

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

easy

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

B. Find the number of zero elements in the matrix.

C. Sort the matrix rows in ascending order.

D. Replace all non-zero elements with 1.

Solution

1. Step 1: Understand the problem requirement

   The problem requires changing the matrix so that any row or column containing a zero is set entirely to zero.

2. Step 2: Note the in-place constraint

   This must be done 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 A

4. Quick Check:

   In-place zeroing of rows and columns = Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space. [OK]

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

Common Mistakes:

• Using extra space like another matrix
• Only zeroing rows or only columns
• Not handling the in-place requirement

2. Which of the following TypeScript code snippets correctly declares a 2D matrix named matrix of numbers?

easy

A. const matrix: number[][] = [[1, 0], [3, 4]];

B. const matrix: number[] = [[1, 0], [3, 4]];

C. const matrix: number = [[1, 0], [3, 4]];

D. const matrix: any = 1, 0, 3, 4;

Solution

1. Step 1: Understand TypeScript 2D array syntax

   A 2D array of numbers is declared as number[][].

2. Step 2: Check each option

   const matrix: number[][] = [[1, 0], [3, 4]]; uses number[][] and initializes correctly. Options B and C use incorrect types. const matrix: any = 1, 0, 3, 4; is invalid syntax.

3. Final Answer:

   const matrix: number[][] = [[1, 0], [3, 4]]; -> Option A

4. Quick Check:

   2D array type is number[][] = const matrix: number[][] = [[1, 0], [3, 4]]; [OK]

Hint: Use number[][] for 2D numeric arrays in TypeScript [OK]

Common Mistakes:

• Using number[] for 2D arrays
• Assigning arrays to number type
• Incorrect syntax for array declaration

3. Given the following TypeScript code, what will be the state of matrix after calling setZeroes(matrix)?

function setZeroes(matrix: number[][]): void {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const rowZero = new Array(rows).fill(false);
  const colZero = new Array(cols).fill(false);

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

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

const matrix = [
  [1, 2, 3],
  [4, 0, 6],
  [7, 8, 9]
];
setZeroes(matrix);
console.log(matrix);

medium

A. [[1, 2, 3], [0, 0, 0], [7, 8, 9]]

B. [[1, 2, 3], [4, 0, 6], [7, 8, 9]]

C. [[1, 0, 3], [0, 0, 0], [7, 0, 9]]

D. [[1, 0, 3], [4, 0, 6], [7, 0, 9]]

Solution

1. Step 1: Identify zero positions

   Zero found at matrix[1][1]. So row 1 and column 1 must be zeroed.

2. Step 2: Apply zeroing to rows and columns

   Row 1 becomes [0,0,0]. Column 1 elements at rows 0 and 2 become 0. Resulting matrix is [[1,0,3],[0,0,0],[7,0,9]].

3. Final Answer:

   [[1, 0, 3], [0, 0, 0], [7, 0, 9]] -> Option C

4. Quick Check:

   Zero at (1,1) zeroes row 1 and column 1 = [[1, 0, 3], [0, 0, 0], [7, 0, 9]] [OK]

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

Common Mistakes:

• Zeroing only rows or only columns
• Not zeroing all affected cells
• Modifying matrix during first scan

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

function setZeroes(matrix: number[][]): void {
  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 only zeros the first row and column.

B. It modifies the matrix while scanning, causing incorrect zeroing.

C. It does not zero the columns correctly.

D. It uses extra space which is not allowed.

Solution

1. Step 1: Analyze matrix modification during iteration

   The code sets zeros immediately when found, changing matrix values during scanning.

2. Step 2: Understand impact of immediate modification

   This causes new zeros to be detected incorrectly, leading to extra rows and columns zeroed.

3. Final Answer:

   It modifies the matrix while scanning, causing incorrect zeroing. -> Option B

4. Quick Check:

   Immediate zeroing during scan causes errors = It modifies the matrix while scanning, causing incorrect zeroing. [OK]

Hint: Mark first, then zero to avoid premature changes [OK]

Common Mistakes:

• Zeroing matrix cells while scanning
• Not using markers to track zero rows/columns
• Assuming immediate zeroing is safe

5. You want to optimize the Set Matrix Zeroes In Place solution to use O(1) extra space by using the first row and first column as markers. Given the matrix:

[
  [1, 2, 0],
  [4, 0, 6],
  [7, 8, 9]
]

What will be the matrix after applying this optimized approach?

hard

A. [[1, 0, 0], [0, 0, 0], [7, 0, 9]]

B. [[1, 2, 0], [4, 0, 6], [7, 8, 9]]

C. [[0, 0, 0], [0, 0, 0], [7, 0, 9]]

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

Solution

1. Step 1: Use first row and column as markers

   Zeros at (0,2) and (1,1) mark first row and column accordingly.

2. Step 2: Zero rows and columns based on markers

   Row 0 and 1 become all zeros. Column 1 and 2 become zeros in all rows. Final matrix is [[0,0,0],[0,0,0],[7,0,0]].

3. Final Answer:

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

4. Quick Check:

   First row/column markers zero rows/columns = [[0, 0, 0], [0, 0, 0], [7, 0, 0]] [OK]

Hint: Use first row/column as flags to save space [OK]

Common Mistakes:

• Not handling first row and column separately
• Overwriting markers too early
• Missing zeros in last row or column