Set Matrix Zeroes In Place in DSA Typescript - Build from Scratch

Set Matrix Zeroes In Place

📖 Scenario: Imagine you have a grid representing a garden with plants. Some plants are dead (marked as 0). You want to mark the entire row and column of any dead plant as dead too, to prepare for replanting.

🎯 Goal: You will write a program to update the garden grid in place. If any cell is 0, set its entire row and column to 0 without using extra space for another grid.

📋 What You'll Learn

Create a 2D array called garden with exact values

Create two boolean variables firstRowHasZero and firstColHasZero

Use the first row and first column of garden to mark rows and columns to be zeroed

Update the garden matrix in place based on these markers

Print the final garden matrix row by row

💡 Why This Matters

🌍 Real World

This technique is useful in image processing, spreadsheets, and grid-based games where you need to mark entire rows and columns based on certain conditions.

💼 Career

Understanding in-place matrix manipulation is important for software engineers working with data transformations, memory optimization, and algorithm design.

1

Create the garden matrix

Create a 2D array called garden with these exact values: [[1,1,1],[1,0,1],[1,1,1]]

DSA Typescript

// Create the 2D array called garden with the given values
// Your code here

Hint

Use const garden: number[][] = [[1,1,1],[1,0,1],[1,1,1]]; to create the matrix.

2

Check if first row and first column have zero

Create two boolean variables called firstRowHasZero and firstColHasZero and set them to false initially

DSA Typescript

const garden: number[][] = [[1,1,1],[1,0,1],[1,1,1]];
// Create boolean variables firstRowHasZero and firstColHasZero and set to false
// Your code here

Hint

Use let firstRowHasZero: boolean = false; and let firstColHasZero: boolean = false;.

3

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

Use for loops and if statements to update firstRowHasZero and firstColHasZero if zeros are found in the first row or first column. Then use nested for loops to mark zeros in the first row and first column for other zeros in the matrix.

DSA Typescript

const garden: number[][] = [[1,1,1],[1,0,1],[1,1,1]];
let firstRowHasZero: boolean = false;
let firstColHasZero: boolean = false;
// Detect zeros in first row and first column
// Mark zeros in first row and column for other zeros
// Your code here

Hint

Check first row and column for zeros. Then mark zeros in first row and column for other zeros.

4

Set zeros in garden based on markers and print result

Use nested for loops starting from index 1 to set garden[i][j] to 0 if garden[i][0] or garden[0][j] is 0. Then set entire first row or first column to 0 if firstRowHasZero or firstColHasZero is true. Finally, print each row of garden using console.log.

DSA Typescript

const garden: number[][] = [[1,1,1],[1,0,1],[1,1,1]];
let firstRowHasZero: boolean = false;
let firstColHasZero: boolean = false;

for (let j = 0; j < garden[0].length; j++) {
    if (garden[0][j] === 0) {
        firstRowHasZero = true;
        break;
    }
}

for (let i = 0; i < garden.length; i++) {
    if (garden[i][0] === 0) {
        firstColHasZero = true;
        break;
    }
}

for (let i = 1; i < garden.length; i++) {
    for (let j = 1; j < garden[0].length; j++) {
        if (garden[i][j] === 0) {
            garden[i][0] = 0;
            garden[0][j] = 0;
        }
    }
}
// Set zeros in garden based on markers and print each row
// Your code here

Hint

Use the markers in first row and column to set zeros. Then update first row and column if needed. Finally, print each row with console.log(garden[i]).

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