Set Matrix Zeroes In Place in DSA Typescript - Deep Dive

Overview - Set Matrix Zeroes In Place

What is it?

Set Matrix Zeroes In Place is a problem where you modify a given 2D matrix so that if any element is zero, its entire row and column become zero. You must do this without using extra space for another matrix. The goal is to update the matrix directly, saving memory. This helps practice careful in-place changes and understanding matrix traversal.

Why it matters

This problem teaches how to efficiently update data structures without extra memory, which is important in real-world systems with limited resources. Without this approach, programs might waste memory or run slower by copying data. Learning this helps write faster, more memory-friendly code, which is crucial for large datasets or embedded systems.

Where it fits

Before this, you should understand basic arrays and matrices, and how to loop through them. After this, you can learn more complex matrix algorithms, space optimization techniques, and in-place data manipulation strategies.

Mental Model

Core Idea

Mark rows and columns that need zeroing using the matrix itself, then update all marked rows and columns to zero without extra space.

Think of it like...

Imagine a classroom seating chart where if one student is absent (zero), the whole row and column of seats become empty to keep everyone spaced out. Instead of writing down all absences separately, you mark the seats directly to remember which rows and columns to clear.

Initial Matrix:
┌─────┬─────┬─────┐
│ 1   │ 0   │ 3   │
├─────┼─────┼─────┤
│ 4   │ 5   │ 6   │
├─────┼─────┼─────┤
│ 7   │ 8   │ 9   │
└─────┴─────┴─────┘

Step 1: Mark first row and column for zeros
Step 2: Update rows and columns based on marks

Resulting Matrix:
┌─────┬─────┬─────┐
│ 0   │ 0   │ 0   │
├─────┼─────┼─────┤
│ 4   │ 0   │ 6   │
├─────┼─────┼─────┤
│ 7   │ 0   │ 9   │
└─────┴─────┴─────┘

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Statement

Concept: Learn what it means to set matrix zeroes in place and why direct modification is required.

You have a matrix (2D array) of numbers. If any number is zero, you must set all numbers in that number's row and column to zero. You must do this without creating a new matrix. For example, if matrix[0][1] is zero, then all elements in row 0 and column 1 become zero.

Result

You understand the goal: zero out rows and columns based on zero elements, modifying the original matrix.

Understanding the problem clearly is essential before trying to solve it, especially the in-place constraint which limits extra memory use.

2

Foundation

Basic Matrix Traversal and Modification

Concept: Learn how to loop through a matrix and change elements.

Use two nested loops: outer loop for rows, inner loop for columns. Access each element by matrix[row][col]. You can read or write values directly. For example, to set matrix[1][2] = 0, just assign it.

Result

You can visit every element and modify it as needed.

Mastering matrix traversal is the foundation for any matrix problem, including this one.

3

Intermediate

Naive Approach: Using Extra Space

🤔Before reading on: do you think using extra space is allowed or not allowed for this problem? Commit to your answer.

Concept: Use extra arrays to remember which rows and columns have zeros, then update the matrix.

Create two arrays: one for rows, one for columns. Traverse the matrix once; if you find a zero, mark its row and column in these arrays. Then traverse the matrix again; if a cell's row or column is marked, set it to zero.

Result

Matrix updated correctly but uses extra memory proportional to rows and columns.

This approach is simple and works but does not meet the in-place requirement, motivating the need for a better method.

4

Intermediate

In-Place Marking Using First Row and Column

🤔Before reading on: do you think it's possible to use the matrix itself to store zero markers? Commit to yes or no.

Concept: Use the first row and first column of the matrix to store markers indicating which rows and columns should be zeroed.

First, check if the first row and first column have any zeros (store these flags separately). Then, for the rest of the matrix, if matrix[i][j] is zero, set matrix[i][0] and matrix[0][j] to zero. These marks tell which rows and columns to zero later.

Result

Markers are stored inside the matrix without extra arrays.

Using the matrix itself for marking saves space and cleverly reuses existing storage.

5

Intermediate

Applying Zeroes Based on Markers

🤔Before reading on: after marking, do you think you should zero rows first or columns first? Commit to your answer.

Concept: Use the markers in the first row and column to set zeros in the rest of the matrix.

Traverse the matrix except the first row and column. If matrix[i][0] or matrix[0][j] is zero, set matrix[i][j] to zero. Then, based on the flags, zero out the first row and/or first column if needed.

Result

Matrix updated correctly with zeroes in all required rows and columns.

Separating marking and updating phases prevents premature zeroing that would lose marker information.

6

Advanced

Handling First Row and Column Edge Cases

🤔Before reading on: do you think the first row and column need special handling? Commit to yes or no.

Concept: Because the first row and column are used as markers, you must separately track if they originally contained zeros to update them correctly at the end.

Use two boolean variables to remember if the first row or first column had any zeros before marking. After updating the rest of the matrix, zero out the first row and/or column if these flags are true.

Result

First row and column are correctly zeroed only if needed, preserving marker information during processing.

Recognizing and handling these edge cases prevents bugs and ensures correctness.

7

Expert

Optimizing for Minimal Writes and Cache Efficiency

🤔Before reading on: do you think writing zeros multiple times affects performance? Commit to yes or no.

Concept: Minimize writes by only updating cells once and consider cache-friendly traversal order to improve speed on large matrices.

After marking, update the matrix in a single pass, avoiding redundant writes. Traverse rows and columns in an order that matches memory layout (row-major) to reduce cache misses. This subtle optimization improves runtime in real systems.

Result

Faster execution with fewer memory writes and better CPU cache usage.

Understanding low-level performance details can make a big difference in real-world applications beyond just correctness.

Under the Hood

The algorithm uses the first row and first column as storage to mark which rows and columns must be zeroed. This avoids extra memory allocation. It first scans the matrix to set these markers, then updates the matrix based on them. Special flags track if the first row or column originally had zeros to avoid losing marker data. This in-place marking leverages the matrix's own memory layout to save space.

Why designed this way?

The problem demands no extra space beyond constant variables. Using the matrix itself as marker storage is a clever tradeoff that avoids additional arrays. Alternatives like copying the matrix or using separate arrays use more memory and are less efficient. This design balances memory use and simplicity.

┌───────────────────────────────┐
│ Original Matrix               │
│ ┌───────────────┐            │
│ │ 1  0  3       │            │
│ │ 4  5  6       │            │
│ │ 7  8  9       │            │
│ └───────────────┘            │
│                               │
│ Step 1: Check first row/col   │
│ Flags: firstRowHasZero = true │
│        firstColHasZero = false│
│                               │
│ Step 2: Mark zeros in first   │
│ row and column:               │
│ matrix[1][0] = 0 if row 1 has │
│ zero, matrix[0][2] = 0 if col │
│ 2 has zero, etc.              │
│                               │
│ Step 3: Update matrix based on│
│ markers                      │
│                               │
│ Step 4: Zero first row/col if │
│ flags are true               │
└───────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Do you think you can zero rows and columns immediately when you find a zero? Commit yes or no.

Common Belief: You can set zeros immediately when you find a zero element during the first scan.

Reality: Setting zeros immediately will overwrite data needed to find other zeros, causing incorrect results.

Why it matters: Immediate zeroing destroys information about other zeros, leading to incomplete or wrong zeroing of rows and columns.

Quick: Do you think using the first row and column as markers will always work without extra flags? Commit yes or no.

Common Belief: You can use the first row and column as markers without separately tracking if they originally had zeros.

Reality: Without separate flags, you cannot distinguish between original zeros and marker zeros in the first row and column, causing errors.

Why it matters: Failing to track original zeros in the first row/column leads to incorrect zeroing, either missing or over-zeroing.

Quick: Do you think the extra space used by arrays for rows and columns is negligible? Commit yes or no.

Common Belief: Using extra arrays for rows and columns is acceptable since they are small compared to the matrix.

Reality: For very large matrices or memory-constrained environments, extra arrays can be costly and violate in-place constraints.

Why it matters: Ignoring space constraints can cause inefficient programs that fail in real systems with limited memory.

Expert Zone

1

The order of updating the matrix after marking is critical to avoid overwriting marker information prematurely.

2

Using boolean flags for the first row and column is a subtle but necessary step to handle edge cases correctly.

3

Cache-friendly traversal order can significantly improve performance on large matrices, a detail often overlooked.

When NOT to use

This in-place method is not suitable if the matrix is immutable or if you need to preserve the original matrix. In such cases, use a copy or extra space. Also, if the matrix is sparse and large, specialized sparse matrix techniques may be better.

Production Patterns

In real systems, this technique is used in image processing to mask pixels, in spreadsheets to clear rows/columns efficiently, and in database engines to mark invalid rows without extra memory. It is also a common interview question to test space optimization skills.

Connections

Bit Manipulation

Both use in-place marking to save space by encoding information within existing data.

Understanding how to store extra information inside existing data structures helps optimize memory usage across domains.

Cache Optimization

The order of matrix traversal affects CPU cache hits, impacting performance.

Knowing how memory access patterns affect speed helps write faster algorithms beyond just correctness.

Spreadsheet Software

Setting rows and columns to zero is similar to clearing rows and columns in spreadsheets based on conditions.

Real-world applications like spreadsheets use similar logic to efficiently update large tables without extra copies.

Common Pitfalls

#1 Zeroing rows and columns immediately when a zero is found.

Wrong approach:

for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
for (let k = 0; k < n; k++) matrix[i][k] = 0;
for (let k = 0; k < m; k++) matrix[k][j] = 0;
}
}
}

Correct approach:

Use markers first, then zero rows and columns after scanning the entire matrix.

Root cause:

Modifying the matrix during scanning destroys information about other zeros.

#2 Not tracking if the first row or column originally had zeros.

Wrong approach:

Use first row and column as markers but skip checking if they had zeros before marking.

Correct approach:

Use boolean flags to remember if first row or column had zeros before marking and update them at the end accordingly.

Root cause:

Confusing original zeros with marker zeros leads to incorrect final matrix.

#3 Using extra arrays despite the problem requiring in-place modification.

Wrong approach:

const rows = new Array(m).fill(false);
const cols = new Array(n).fill(false);
// Use these arrays to mark zeros

Correct approach:

Use the first row and column of the matrix itself to store markers, avoiding extra arrays.

Root cause:

Not understanding or ignoring the in-place constraint.

Key Takeaways

Set Matrix Zeroes In Place requires modifying the matrix directly without extra memory by cleverly using the first row and column as markers.

Separating the marking phase from the updating phase prevents losing information and ensures correctness.

Special care is needed to handle the first row and column because they serve dual roles as data and markers.

Understanding memory and cache behavior can optimize performance beyond just solving the problem correctly.

This problem teaches a valuable pattern of in-place data modification applicable in many real-world scenarios.

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