Set Matrix Zeroes In Place in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the "Set Matrix Zeroes In Place" problem ask you to do?

You need to change a given matrix so that if any element is 0, its entire row and column become 0, without using extra space for another matrix.

intermediate

Why do we use the first row and first column of the matrix in the in-place solution?

They act as markers to remember which rows and columns should be set to zero later, avoiding extra space usage.

intermediate

In the in-place approach, what special care must be taken for the first row and first column?

We must separately track if the first row or first column originally had any zeroes, because they are used as markers and will be overwritten.

beginner

What is the time complexity of the in-place solution for setting matrix zeroes?

O(m * n), where m is the number of rows and n is the number of columns, because we scan the matrix multiple times but each scan is linear.

beginner

What is the space complexity of the in-place solution for the Set Matrix Zeroes problem?

O(1) extra space, since we only use the matrix itself and a few variables for tracking, no additional matrix or arrays.

What is the main idea behind the in-place solution for Set Matrix Zeroes?

A Sort the matrix rows and columns

B Create a new matrix to store zero positions

C Use a hash map to store zero positions

D Use the first row and column as markers to track zero rows and columns

The in-place solution cleverly uses the first row and column of the matrix to mark which rows and columns should be zeroed, avoiding extra space.

Why do we need to separately track if the first row has zeroes?

A Because the first row is used as a marker and might be overwritten

B Because the first row is always zero

C Because the first row cannot have zeroes

D Because the first row is not part of the matrix

Since the first row is used to mark zero columns, we must remember if it originally had zeroes to correctly zero it later.

What happens if you forget to track the first column zeroes separately?

A You might incorrectly zero the first column or miss zeroing it

B The algorithm will run faster

C The matrix will remain unchanged

D The matrix will be sorted

Not tracking the first column zeroes separately can cause wrong zeroing because the first column is used as a marker.

What is the space complexity of the in-place Set Matrix Zeroes solution?

A O(m + n)

B O(m * n)

C O(1)

D O(log(m * n))

The in-place solution uses constant extra space by reusing the matrix for markers.

Which step is done last in the in-place Set Matrix Zeroes algorithm?

A Marking zero rows and columns

B Zeroing the first row and first column if needed

C Scanning the matrix for zeroes

D Returning the matrix

Zeroing the first row and column is done last to avoid overwriting markers too early.

Explain how the in-place algorithm for Set Matrix Zeroes uses the first row and column as markers.

Think about how to remember zero positions without extra space.

Describe the steps to set matrix zeroes in place without using extra space.

Follow the order of scanning, marking, and zeroing carefully.

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