Why Set Matrix Zeroes In Place in DSA C?

The Big Idea

What if you could fix a whole broken row and column in a giant grid with just one smart pass?

The Scenario

Imagine you have a big spreadsheet with numbers. If any cell has zero, you want to make its entire row and column zero. Doing this by hand means checking every cell again and again, which takes forever.

The Problem

Manually changing rows and columns is slow and confusing. You might miss some cells or change cells too early, causing wrong results. It's easy to make mistakes and waste time.

The Solution

This method lets you mark which rows and columns need to be zeroed without extra space. Then you update the matrix all at once, saving time and avoiding errors.

Before vs After

✗ Before

for (int i = 0; i < rows; i++) {
  for (int j = 0; j < cols; j++) {
    if (matrix[i][j] == 0) {
      // set entire row and column to zero immediately
    }
  }
}

✓ After

for (int i = 0; i < rows; i++) {
  for (int j = 0; j < cols; j++) {
    if (matrix[i][j] == 0) {
      // mark row i and column j
    }
  }
}
// update matrix using marks

What It Enables

You can quickly update large grids to zero out rows and columns without extra memory or mistakes.

Real Life Example

In image processing, if a pixel is corrupted (zero), you want to clear its entire row and column to avoid errors in the final picture.

Key Takeaways

Manual zeroing is slow and error-prone.

Marking rows and columns first avoids early changes.

In-place update saves memory and time.

Practice

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

easy

A. Count the number of zero elements in the matrix.

B. Find the sum of all elements in the matrix.

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

D. Sort each row of the matrix in ascending order.

Solution

1. Step 1: Understand the problem requirement

   The problem asks to change the matrix so that any row or column containing a zero should be set entirely to zero.

2. Step 2: Note the constraint of in-place modification

   The matrix must be modified 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 C

4. Quick Check:

   Set matrix zeroes in place = Modify matrix rows and columns with zeros [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 modifying the matrix in place

2. Which of the following C code snippets correctly declares a 3x3 matrix to be used for the Set Matrix Zeroes problem?

easy

A. int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};

B. int matrix[3] = {1,2,3,4,5,6,7,8,9};

C. int matrix[][] = {{1,2,3},{4,5,6},{7,8,9}};

D. int matrix[3][3] = {1,2,3,4,5,6,7,8};

Solution

1. Step 1: Check correct 2D array declaration syntax in C

   In C, a 2D array must have fixed sizes for both dimensions, and initialization uses nested braces.

2. Step 2: Validate each option

   int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}}; correctly declares and initializes a 3x3 matrix. int matrix[3] = {1,2,3,4,5,6,7,8,9}; is a 1D array with too many elements. int matrix[][] = {{1,2,3},{4,5,6},{7,8,9}}; misses size for second dimension. int matrix[3][3] = {1,2,3,4,5,6,7,8}; has too few initializers (matrix[2][2] uninitialized).

3. Final Answer:

   int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}}; -> Option A

4. Quick Check:

   Correct 2D array syntax = int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}}; [OK]

Hint: Use nested braces for 2D array initialization [OK]

Common Mistakes:

• Missing size for second dimension
• Using 1D array for 2D data
• Incorrect initializer braces

3. What will be the matrix after running the in-place zeroing algorithm on this 3x3 matrix?

int matrix[3][3] = {
  {1, 0, 3},
  {4, 5, 6},
  {7, 8, 9}
};

medium

A. [[1, 0, 3], [4, 5, 6], [7, 8, 9]]

B. [[0, 0, 0], [4, 0, 6], [7, 0, 9]]

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

D. [[0, 0, 0], [4, 5, 6], [0, 0, 0]]

Solution

1. Step 1: Identify zero positions in original matrix

   Zero is at position (0,1). So row 0 and column 1 must be zeroed.

2. Step 2: Set entire row 0 and column 1 to zero

   Row 0 becomes [0,0,0]. Column 1 elements at rows 1 and 2 become 0, so matrix[1][1]=0 and matrix[2][1]=0.

3. Final Answer:

   [[0, 0, 0], [4, 0, 6], [7, 0, 9]] -> Option B

4. Quick Check:

   Zero at (0,1) zeroes row 0 and col 1 = [[0, 0, 0], [4, 0, 6], [7, 0, 9]] [OK]

Hint: Zero row and column of each zero element [OK]

Common Mistakes:

• Zeroing entire matrix
• Missing zeroing column elements
• Not zeroing row elements

4. Consider this code snippet for setting matrix zeroes in place. What is the main bug?

void setZeroes(int matrix[3][3]) {
  int i, j;
  for(i=0; i<3; i++) {
    for(j=0; j<3; j++) {
      if(matrix[i][j] == 0) {
        for(int k=0; k<3; k++) {
          matrix[i][k] = 0;
          matrix[k][j] = 0;
        }
      }
    }
  }
}

medium

A. It uses wrong loop bounds causing out-of-bounds access.

B. It does not check for zeros at all.

C. It uses extra space which is not allowed.

D. It modifies zeros immediately causing cascading zeroing and incorrect results.

Solution

1. Step 1: Analyze immediate zeroing inside nested loops

   The code sets zeros immediately when it finds a zero, which changes matrix during iteration.

2. Step 2: Understand cascading zeroing problem

   New zeros created cause further zeroing in the same pass, leading to incorrect results.

3. Final Answer:

   It modifies zeros immediately causing cascading zeroing and incorrect results. -> Option D

4. Quick Check:

   Immediate zeroing causes cascading errors = It modifies zeros immediately causing cascading zeroing and incorrect results. [OK]

Hint: Mark zeros first, then update matrix after [OK]

Common Mistakes:

• Zeroing matrix while scanning
• Not separating marking and updating steps
• Assuming immediate zeroing is safe

5. Given a 4x4 matrix:

int matrix[4][4] = {
  {1, 2, 3, 4},
  {5, 0, 7, 8},
  {9, 10, 11, 12},
  {0, 14, 15, 16}
};

Which is the correct matrix after applying the optimal in-place zeroing algorithm using first row and column as markers?

hard

A. [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]]

B. [[1, 0, 3, 4], [0, 0, 0, 0], [9, 0, 11, 12], [0, 0, 0, 0]]

C. [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

D. [[1, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12], [0, 14, 15, 16]]

Solution

1. Step 1: Identify zero positions

   Zeros at (1,1) and (3,0).

2. Step 2: Determine first row and first column zero flags

   First row: no zeros (firstRowZero = false). First column: zero at (3,0) (firstColZero = true).

3. Step 3: Mark zeros using first row and column (inner matrix)

   Scan i=1 to 3, j=1 to 3: (1,1)=0 sets matrix[1][0]=0, matrix[0][1]=0.

4. Step 4: Zero inner matrix using marks

   For i=1 to 3, j=1 to 3: if matrix[i][0]==0 or matrix[0][j]==0, set matrix[i][j]=0. Zeros row 1 (mark at [1][0]), col 1 (mark at [0][1]), row 3 (orig [3][0]=0).

5. Step 5: Apply flags to borders

   First row unchanged (false). First col all zeroed (true): matrix[0][0]=0, matrix[2][0]=0 (among others).

6. Final Answer:

   [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] -> Option A

7. Quick Check:

   Zeros at (1,1),(3,0) zero rows 1&3, cols 0&1 = [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] [OK]

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

Common Mistakes:

• Zeroing entire first row or column incorrectly
• Not marking zeros properly
• Overwriting markers too early