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

Set Matrix Zeroes In Place

📖 Scenario: You are working with a grid of numbers representing a game board. Sometimes, certain cells become inactive and are marked with zero. To keep the board consistent, if any cell is zero, the entire row and column of that cell should become zero.

🎯 Goal: Modify the given matrix in place so that if any cell is zero, its entire row and column are set to zero. You will do this without using extra space for another matrix.

📋 What You'll Learn

Create a 2D integer array called matrix with the exact values given.

Create two integer variables rows and cols to store the matrix dimensions.

Implement the in-place algorithm to set matrix zeroes using the first row and first column as markers.

Print the matrix after modification in the specified format.

💡 Why This Matters

🌍 Real World

This technique is useful in image processing, game boards, and spreadsheet applications where certain cells becoming inactive affect entire rows and columns.

💼 Career

Understanding in-place matrix modification is important for software engineers working with memory-efficient algorithms and data manipulation.

1

Create the matrix

Create a 2D integer array called matrix with 3 rows and 4 columns containing these exact values: {{1, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 1, 1}}.

DSA C

# Create the matrix with the given values
// Your code here

Hint

Use a 2D array with 3 rows and 4 columns and fill it with the exact numbers given.

2

Set matrix dimensions

Create two integer variables called rows and cols and set them to 3 and 4 respectively to represent the matrix size.

DSA C

int matrix[3][4] = {
    {1, 1, 1, 0},
    {1, 0, 1, 1},
    {1, 1, 1, 1}
};

// Set rows and cols variables
// Your code here

Hint

Use two integer variables to store the number of rows and columns.

3

Implement in-place zero setting

Write code to set matrix zeroes in place using the first row and first column as markers. Use variables rows and cols for dimensions and modify matrix accordingly.

DSA C

int matrix[3][4] = {
    {1, 1, 1, 0},
    {1, 0, 1, 1},
    {1, 1, 1, 1}
};

int rows = 3;
int cols = 4;

// Implement the in-place zero setting algorithm
// Your code here

Hint

Use the first row and first column as markers to remember which rows and columns should be zeroed. Then update the matrix accordingly.

4

Print the modified matrix

Print the matrix after modification. Use nested loops with variables i and j to print each element separated by spaces, and print a newline after each row.

DSA C

Hint

Use nested loops to print each element separated by spaces. Print a newline after each row.

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