Set Matrix Zeroes In Place in DSA C# - Time & Space Complexity

Time Complexity: Set Matrix Zeroes In Place

O(rows x cols)

Understanding Time Complexity

We want to understand how the time needed to set matrix zeroes grows as the matrix size increases.

Specifically, how the operations scale when we mark rows and columns to zero in place.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void SetZeroes(int[][] matrix) {
    int rows = matrix.Length;
    int cols = matrix[0].Length;
    bool firstColHasZero = false;

    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) firstColHasZero = true;
        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 (matrix[0][0] == 0) {
        for (int j = 0; j < cols; j++) matrix[0][j] = 0;
    }

    if (firstColHasZero) {
        for (int i = 0; i < rows; i++) matrix[i][0] = 0;
    }
}
    

This code sets entire rows and columns to zero if any element in them is zero, modifying the matrix in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops traversing the matrix elements.
• How many times: Each nested loop runs over all rows and columns, roughly rows x columns times.

How Execution Grows With Input

As the matrix size grows, the number of operations grows roughly with the total number of elements.

Input Size (n x m)	Approx. Operations
10 x 10	About 200 (two passes over 100 elements)
100 x 100	About 20,000 (two passes over 10,000 elements)
1000 x 1000	About 2,000,000 (two passes over 1,000,000 elements)

Pattern observation: Operations grow proportionally to the number of elements in the matrix.

Final Time Complexity

Time Complexity: O(rows x cols)

This means the time needed grows linearly with the total number of elements in the matrix.

Common Mistake

[X] Wrong: "Since there are nested loops, the time complexity must be quadratic like O(n²) regardless of matrix shape."

[OK] Correct: The nested loops cover rows and columns, so the complexity depends on both dimensions multiplied, not just one squared. For non-square matrices, this matters.

Interview Connect

Understanding this complexity helps you explain how your solution scales with matrix size, a key skill in interviews.

Self-Check

"What if we used extra space to store zero rows and columns instead of modifying in place? How would the time complexity change?"

Practice

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

easy

A. Replace all zeroes with ones in the matrix.

B. Count the number of zeroes 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 set entire rows and columns to zero if any element in them is zero, modifying the matrix directly without extra space.

2. Step 2: Differentiate from other operations

   Counting zeroes, replacing zeroes with ones, or sorting rows do not meet the problem's goal.

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:

   Goal is to set rows and columns zero in place = A [OK]

Hint: Focus on zero elements affecting rows and columns without extra space [OK]

Common Mistakes:

• Thinking the problem is about counting zeroes
• Trying to use extra memory like new arrays
• Confusing zero replacement with sorting

2. Which of the following C# code snippets correctly declares a 2D integer matrix named matrix with 3 rows and 3 columns?

easy

A. int[,] matrix = new int[3,3];

B. int[][] matrix = new int[3][3];

C. int matrix[3,3];

D. int[] matrix = new int[3,3];

Solution

1. Step 1: Recall C# 2D array syntax

   In C#, a rectangular 2D array is declared as int[,] matrix = new int[3,3];.

2. Step 2: Identify incorrect syntax

   int[][] matrix = new int[3][3]; uses jagged array syntax incorrectly, C is invalid in C#, and D has type mismatch.

3. Final Answer:

   int[,] matrix = new int[3,3]; -> Option A

4. Quick Check:

   Correct 2D array declaration = A [OK]

Hint: Use int[,] for 2D arrays, not jagged or invalid syntax [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Missing array type in declaration
• Using C/C++ style array declaration

3. What will be the state of the matrix after running the following C# code?

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

// Set matrix zeroes in place
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);

bool firstRowZero = false;
bool firstColZero = false;

// Check first row
for (int j = 0; j < cols; j++) {
    if (matrix[0, j] == 0) firstRowZero = true;
}
// Check first column
for (int i = 0; i < rows; i++) {
    if (matrix[i, 0] == 0) firstColZero = true;
}

// Use first row and column as markers
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;
        }
    }
}

// Set zeroes based on markers
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;
        }
    }
}

// Set first row zero if needed
if (firstRowZero) {
    for (int j = 0; j < cols; j++) matrix[0, j] = 0;
}
// Set first column zero if needed
if (firstColZero) {
    for (int i = 0; i < rows; i++) matrix[i, 0] = 0;
}

medium

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

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

C. [[1, 0, 3], [0, 0, 0], [7, 0, 0]]

D. [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Solution

1. Step 1: Identify zero positions and mark rows and columns

   Zero found at matrix[1,1]. Mark matrix[1,0] and matrix[0,1] as zero.

2. Step 2: Set zeroes based on markers

   Set matrix[1,j] and matrix[i,1] to zero for i,j > 0. First row and column have no zero, so no change there.

3. Final Answer:

   [[1, 0, 3], [0, 0, 0], [7, 0, 9]] -> Option B

4. Quick Check:

   Zero at (1,1) sets row 1 and col 1 zero = A [OK]

Hint: Mark zero rows and columns using first row/column as flags [OK]

Common Mistakes:

• Not marking first row and column correctly
• Setting zeroes before marking all zero positions
• Overwriting first row/column too early

4. The following code attempts to set matrix zeroes in place but has a bug. What is the bug?

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

int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);

bool firstRowZero = false;
bool firstColZero = false;

// Check first row
for (int j = 0; j < cols; j++) {
    if (matrix[0, j] == 0) firstRowZero = true;
}
// Check first column
for (int i = 0; i < rows; i++) {
    if (matrix[i, 0] == 0) firstColZero = true;
}

// Use first row and column as markers
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;
        }
    }
}

// Set zeroes based on markers
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;
        }
    }
}

// Set first row zero if needed
if (firstRowZero) {
    for (int j = 0; j < cols; j++) matrix[0, j] = 0;
}
// Set first column zero if needed
if (firstColZero) {
    for (int i = 0; i < rows; i++) matrix[i, 0] = 0;
}

medium

A. The first row zero check is done after modifying the matrix, causing incorrect results.

B. The first column zero check is missing.

C. The code does not mark zeroes in the first row and column correctly.

D. The code does not handle the case when the first element matrix[0,0] is zero.

Solution

1. Step 1: Understand the role of matrix[0,0]

   matrix[0,0] is used to mark both first row and first column zero status, but here separate booleans are used.

2. Step 2: Identify missing handling of matrix[0,0]

   If matrix[0,0] is zero, it affects both first row and column, but code only uses booleans, so it may miss this case.

3. Final Answer:

   The code does not handle the case when the first element matrix[0,0] is zero. -> Option D

4. Quick Check:

   matrix[0,0] zero affects both row and column flags = C [OK]

Hint: Remember matrix[0,0] marks both first row and column zero [OK]

Common Mistakes:

• Ignoring matrix[0,0] special role
• Checking first row/column after modifying matrix
• Not using separate flags for first row and column

5. Given a matrix:

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

Apply the Set Matrix Zeroes In Place algorithm. What is the final matrix state?

hard

A. [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

B. [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]

C. [[0, 0, 0, 0], [3, 0, 0, 0], [1, 0, 0, 0]]

D. [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Solution

1. Step 1: Identify zeroes and mark rows and columns

   Zeroes at matrix[0,0] and matrix[0,3]. Mark first row and columns 0 and 3.

2. Step 2: Set zeroes based on markers

   Set entire first row zero. Set columns 0 and 3 zero in all rows.

3. Final Answer:

   [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]] -> Option A

4. Quick Check:

   Zeroes in first row set cols 0 and 3 zero = B [OK]

Hint: Zero in first row sets entire row and columns zero [OK]

Common Mistakes:

• Not zeroing columns 0 and 3 in all rows
• Leaving first row partially unchanged
• Confusing zeroing rows vs columns