Set Matrix Zeroes In Place in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the problem 'Set Matrix Zeroes In Place' ask you to do?

It asks to modify a given matrix so that if an element is 0, its entire row and column are set to 0, without using extra space for another matrix.

intermediate

Why do we use the first row and first column of the matrix in the in-place solution?

They are used as markers to remember which rows and columns should be zeroed, avoiding extra space usage.

intermediate

What is the main challenge when setting matrix zeroes in place?

The challenge is to mark rows and columns to be zeroed without losing original information and without extra space.

intermediate

In the in-place approach, why do we handle the first row and first column separately at the end?

Because they are used as markers, we must update them last to avoid overwriting marker information prematurely.

intermediate

What is the time and space complexity of the in-place solution for 'Set Matrix Zeroes'?

Time complexity is O(m*n) where m and n are matrix dimensions; space complexity is O(1) as no extra matrix is used.

What is the purpose of using the first row and first column in the in-place solution?

A To increase matrix size

B To store the original matrix values

C To avoid modifying the matrix

D To store which rows and columns should be zeroed

The first row and column are used as markers to remember which rows and columns need to be set to zero.

What should you do first when scanning the matrix in the in-place approach?

A Mark zeros in the first row and column

B Set all zeros immediately

C Copy the matrix

D Ignore zeros

First, mark the rows and columns that contain zeros by setting the first row and column cells.

Why do we need to check if the first row or first column originally had zeros?

A To decide if they should be zeroed at the end

B To skip them during processing

C To copy them to another matrix

D To delete them

Because the first row and column are used as markers, we must remember if they originally had zeros to zero them at the end.

What is the space complexity of the in-place solution?

A O(m*n)

B O(m+n)

C O(1)

D O(log(m*n))

The in-place solution uses constant extra space, O(1), by reusing the matrix itself for marking.

Which step comes last in the in-place algorithm?

A Marking zeros in the matrix

B Zeroing the first row and first column if needed

C Scanning the matrix for zeros

D Returning the matrix

Zeroing the first row and column is done last to avoid losing marker information.

Explain how to set matrix zeroes in place without using extra space.

Think about how to remember which rows and columns to zero without extra memory.

Describe the challenges and solutions in the in-place approach for setting matrix zeroes.

Focus on how to mark and update the matrix carefully.

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. Modify the matrix so that if an element is 0, its entire row and column become 0 without using extra space.

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

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

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.

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

   We must do this 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 B

4. Quick Check:

   Goal = Set rows and columns to zero in-place [OK]

Hint: Remember: zero means zero entire row and column in-place [OK]

Common Mistakes:

• Using extra space like another matrix
• Only zeroing rows or columns, not both
• Not modifying the matrix in-place

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

easy

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

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

C. int matrix[3][4];

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

Solution

1. Step 1: Recall Java 2D array declaration syntax

   In Java, 2D arrays are declared as int[][] name = new int[rows][columns];.

2. Step 2: Match the correct dimensions

   int[][] matrix = new int[3][4]; uses 3 rows and 4 columns correctly. int matrix[][] = new int[4][3]; reverses dimensions, C is invalid syntax, D misses array brackets.

3. Final Answer:

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

4. Quick Check:

   Java 2D array syntax = int[][] matrix = new int[3][4]; [OK]

Hint: Use int[][] for 2D arrays with new int[rows][cols] [OK]

Common Mistakes:

• Swapping rows and columns in new int[][]
• Using C-style array declaration
• Missing brackets in declaration

3. What will be the state of the matrix after running the following Java code snippet for setting matrix zeroes in place?

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

// After applying setZeroes(matrix) method
// (method sets entire row and column to zero if element is zero)

medium

A. [[0, 0, 0], [4, 0, 0], [0, 0, 0]]

B. [[1, 0, 0], [4, 0, 0], [0, 0, 0]]

C. [[0, 0, 0], [4, 5, 0], [0, 0, 0]]

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

Solution

1. Step 1: Identify zero elements and their rows and columns

   Zeros are at positions (0,2) and (2,1). Rows 0 and 2, columns 1 and 2 must be zeroed.

2. Step 2: Set entire rows and columns to zero

   Row 0 becomes [0,0,0], row 2 becomes [0,0,0]. Column 1 and 2 in row 1 become 0, so row 1 becomes [4,0,0].

3. Final Answer:

   [[0, 0, 0], [4, 0, 0], [0, 0, 0]] -> Option A

4. Quick Check:

   Zero rows and columns set correctly = [[0, 0, 0], [4, 0, 0], [0, 0, 0]] [OK]

Hint: Mark zero rows and columns first, then update matrix [OK]

Common Mistakes:

• Only zeroing rows or columns, not both
• Not updating all affected cells
• Overwriting zeros too early

4. Consider this buggy Java code snippet for setting matrix zeroes in place:

public void setZeroes(int[][] matrix) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  boolean[] rowZero = new boolean[rows];
  boolean[] colZero = new boolean[cols];

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (matrix[i][j] == 0) {
        rowZero[i] = true;
        colZero[j] = true;
      }
    }
  }

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (rowZero[i] || colZero[j]) {
        matrix[i][j] = 0;
      }
    }
  }
}

What is the main issue with this code regarding the problem constraints?

medium

A. It modifies the matrix before checking all zeros, causing incorrect results.

B. It does not correctly identify zero elements in the matrix.

C. It causes an ArrayIndexOutOfBoundsException.

D. It uses extra space proportional to rows and columns, violating in-place requirement.

Solution

1. Step 1: Analyze space usage of the code

   The code uses two boolean arrays, rowZero and colZero, sized by rows and columns, which is extra space.

2. Step 2: Compare with problem constraints

   The problem requires in-place modification without extra space, so using these arrays violates the constraint.

3. Final Answer:

   It uses extra space proportional to rows and columns, violating in-place requirement. -> Option D

4. Quick Check:

   Extra space used = violates in-place [OK]

Hint: Avoid extra arrays; use matrix first row/column as markers [OK]

Common Mistakes:

• Ignoring space constraints
• Using extra arrays for marking
• Not handling first row/column carefully

5. You have a 4x4 matrix:

1 2 3 4
5 0 7 8
9 10 11 12
0 14 15 16

Using the in-place method for setting matrix zeroes, what will be the matrix after the operation?

hard

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

B. [[0, 0, 0, 4], [0, 0, 0, 0], [0, 0, 0, 12], [0, 0, 0, 0]]

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

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

Solution

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

   Zeros at (1,1) and (3,0). Rows 1 and 3, columns 0 and 1 must be zeroed.

2. Step 2: Set zeros for affected rows and columns

   Rows 1 and 3 become entirely zeros. Columns 0 and 1 become zeros across all rows, resulting in row 0: [0,0,3,4]; row 2: [0,0,11,12].

3. Final Answer:

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

4. Quick Check:

   Zero rows and columns updated correctly = [[0, 0, 3, 4], [0, 0, 0, 0], [0, 0, 11, 12], [0, 0, 0, 0]] [OK]

Hint: Mark first row/column, then update matrix carefully [OK]

Common Mistakes:

• Zeroing entire rows or columns unnecessarily
• Missing zeros in some cells
• Not handling first row and column markers properly