Set Matrix Zeroes In Place in DSA Typescript - 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 scan the matrix to find zeros, mark their rows and columns, then update the matrix in place to set those rows and columns to zero.

Execution Sample

DSA Typescript

function setZeroes(matrix: number[][]): void {
  const m = matrix.length, n = matrix[0].length;
  let firstRowZero = false, firstColZero = false;
  // Mark zeros in first row and column
  // Update matrix based on marks
}

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

Execution Table

Step	Operation	Matrix State	Marks in First Row/Col	Visual State
1	Initial matrix	[[1,1,1],[1,0,1],[1,1,1]]	firstRowZero=false, firstColZero=false	1 1 1 1 0 1 1 1 1
2	Check first row for zero	[[1,1,1],[1,0,1],[1,1,1]]	firstRowZero=false	No zero in first row
3	Check first column for zero	[[1,1,1],[1,0,1],[1,1,1]]	firstColZero=false	No zero in first column
4	Scan rest of matrix for zeros and mark	[[1,0,1],[0,0,1],[1,1,1]]	Mark matrix[1][0]=0, matrix[0][1]=0	Marks: first row col 1=0, first col row 1=0
5	Set zeros based on marks (excluding first row/col)	[[1,0,1],[0,0,0],[1,0,1]]	Marks unchanged	Row 1 and Col 1 set to zero
6	Set first row zero if needed	[[1,0,1],[0,0,0],[1,0,1]]	firstRowZero=false	No change to first row
7	Set first column zero if needed	[[1,0,1],[0,0,0],[1,0,1]]	firstColZero=false	No change to first column
8	End	[[1,0,1],[0,0,0],[1,0,1]]	Done	Final matrix

💡 All rows and columns with zeros updated in place

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
firstRowZero	false	false	false	false	false	false
firstColZero	false	false	false	false	false	false
matrix	[[1,1,1],[1,0,1],[1,1,1]]	[[1,1,1],[1,0,1],[1,1,1]]	[[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 check the first row and first column separately before marking?

Because we use the first row and column to store marks, we must know if they originally had zeros to update them correctly later, as shown in steps 2 and 3.

Why do we mark zeros in the first row and column instead of using extra space?

Marking in the first row and column allows us to track which rows and columns to zero without extra memory, as seen in step 4 where marks are placed.

Why do we update the matrix after marking instead of immediately setting zeros?

Immediate zeroing would affect detection of other zeros. Marking first preserves original zero positions, then we update safely in step 5.

Visual Quiz - 3 Questions

Look at the execution table at step 4, which cells are marked zero in the first row and first column?

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

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

C matrix[0][2] and matrix[2][0]

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

💡 Hint

Check the 'Marks in First Row/Col' column at step 4 in the execution table.

At which step does the matrix first get updated with zeros based on marks?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look at the 'Operation' and 'Matrix State' columns to see when zeros are applied.

If the first row had a zero originally, what variable would be true after step 2?

A firstColZero

B matrix[0][0]

C firstRowZero

D No variable changes

💡 Hint

Refer to the 'variable_tracker' and 'execution_table' step 2 about first row zero check.

Concept Snapshot

Set Matrix Zeroes In Place:
- Scan matrix to find zeros
- Use first row and column as markers
- Mark rows and columns to zero
- Update matrix based on markers
- Handle first row and column separately
- Modify matrix in place without extra space

Full Transcript

We start with a matrix and want to set entire rows and columns to zero if any cell is zero. First, we check if the first row or first column has any zeros and record that in variables. Then, we scan the rest of the matrix. When we find a zero, we mark its row and column by setting the corresponding first row and first column cells to zero. After marking, we update the matrix cells to zero based on these marks, excluding the first row and column. Finally, if the first row or column originally had zeros, we set them to zero as well. This approach modifies the matrix in place without extra memory.

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