Set Matrix Zeroes In Place in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the matrix after running this code?

Consider the following C code that sets entire rows and columns to zero if an element is zero. What will be the printed matrix after execution?

DSA C

void setZeroes(int matrix[3][3], int rows, int cols) {
    int rowFlag = 0, colFlag = 0;
    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) colFlag = 1;
    }
    for (int j = 0; j < cols; j++) {
        if (matrix[0][j] == 0) rowFlag = 1;
    }
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if (colFlag) {
        for (int i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
    if (rowFlag) {
        for (int j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }
}

int main() {
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 0, 6},
        {7, 8, 9}
    };
    setZeroes(matrix, 3, 3);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

A [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

B [[1, 0, 3], [0, 0, 0], [7, 0, 9]]

C [[1, 2, 3], [4, 0, 6], [7, 8, 9]]

D [[1, 0, 3], [0, 0, 0], [0, 0, 0]]

💡 Hint

Check how the first row and first column are used as markers and how the flags affect them.

The code uses the first row and first column to mark which rows and columns should be zeroed. The zero at matrix[1][1] sets matrix[1][0] and matrix[0][1] to zero. Then, all elements in row 1 and column 1 except the first row and column are set to zero. The first row and column are updated last based on flags. Here, neither flag is set because there were no original zeros in the first row or first column.

❓ Predict Output

intermediate

What is the output after setting zeroes in this 4x4 matrix?

Given the following matrix and the same setZeroes function, what is the matrix after the function call?

DSA C

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

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]]

💡 Hint

Remember the first row and column are markers and flags control zeroing of them.

Zeros at matrix[1][1] and matrix[3][0] mark row 1, row 3, column 1, and column 0 for zeroing. The first row and column flags are set accordingly. After processing, rows 1 and 3 and columns 0 and 1 are zeroed except the first row and column which are zeroed last based on flags.

🔧 Debug

advanced

Why does this code cause incorrect zeroing in some cases?

This code attempts to set matrix zeroes in place but sometimes fails. What is the main logical error?

DSA C

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

A It only zeroes rows but not columns.

B It does not check for zeros in the first row and column separately.

C It uses double pointers incorrectly causing segmentation faults.

D It modifies the matrix while scanning, causing new zeros to affect later iterations incorrectly.

💡 Hint

Think about what happens when you change the matrix while looping through it.

The code zeroes rows and columns immediately when it finds a zero. This changes the matrix during iteration, causing zeros introduced by zeroing to trigger more zeroing incorrectly. The correct approach is to mark first, then zero after scanning.

❓ Predict Output

advanced

What is the output of this 2x2 matrix after setZeroes?

Given this 2x2 matrix and the setZeroes function, what is the matrix after execution?

DSA C

int matrix[2][2] = {
    {0, 1},
    {1, 1}
};
setZeroes(matrix, 2, 2);

A [[0, 0], [1, 1]]

B [[0, 0], [0, 0]]

C [[0, 0], [0, 1]]

D [[0, 1], [1, 1]]

💡 Hint

Check how the first row and first column flags affect zeroing.

The zero at matrix[0][0] sets the first row and first column flags. The first column flag is set, so the first column is zeroed. The first row flag is also set, so the first row is zeroed. But since only matrix[0][0] is zero, only the first row and column are zeroed accordingly. The element matrix[1][1] remains 1.

🧠 Conceptual

expert

Why is using the first row and column as markers optimal for in-place zeroing?

In the in-place set matrix zeroes algorithm, why do we use the first row and first column to store markers instead of extra memory?

A It reduces space complexity to O(1) by reusing existing matrix space without extra arrays.

B It simplifies the code by avoiding nested loops.

C It improves time complexity from O(n^3) to O(n^2).

D It allows parallel processing of rows and columns.

💡 Hint

Think about memory usage and how markers are stored.

Using the first row and column as markers avoids allocating extra arrays for rows and columns to be zeroed. This keeps space complexity constant (O(1)) while maintaining time complexity at O(n*m).

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