Set Matrix Zeroes

📋

Problem

Imagine a spreadsheet where any cell containing zero causes its entire row and column to be cleared to zero, simulating a cascading failure in a system.

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. You must do it in place.

m == matrix.lengthn == matrix[0].length1 ≤ m, n ≤ 200-2³31 ≤ matrix[i][j] ≤ 2³1 - 1

Edge cases: Matrix with no zeros → matrix remains unchangedMatrix with all zeros → matrix remains all zerosMatrix with zeros only in first row or first column → ensure flags do not overwrite prematurely

</>

IDE

def setZeroes(matrix: list[list[int]]) -> None:public void setZeroes(int[][] matrix)void setZeroes(vector<vector<int>>& matrix)function setZeroes(matrix)

def setZeroes(matrix):
    # Write your solution here
    pass

class Solution {
    public void setZeroes(int[][] matrix) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    // Write your solution here
}

function setZeroes(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[0,0,0],[0,0,0],[0,0,0]]Zeroed entire matrix immediately upon finding any zero, ignoring correct row/column boundaries.✅ Mark rows and columns first, then zero only those marked rows and columns in a separate pass.

Wrong: [[1,1,1],[1,0,1],[1,1,1]]Did not modify matrix at all after detecting zeros.✅ After marking rows and columns, update matrix cells to zero accordingly.

Wrong: [[0,2,3],[4,5,6],[7,8,9]]Zeroed only the zero cell itself, not entire row and column.✅ Zero entire row and column for each zero found, using flags to avoid repeated zeroing.

Wrong: [[0,0,0,0],[3,4,5,2],[1,3,1,5]]Overwrote first row flags prematurely causing incorrect zeroing.✅ Use separate boolean flags to track if first row and first column originally contained zeros before marking.

Wrong: [[1,0,3],[4,0,6],[0,8,9]]Greedy zeroing on first zero found caused cascading zeroing errors.✅ Use two-pass approach: first mark zeros, then zero rows and columns in second pass.

✓

Test Cases

Focus on handling matrices with no zeros and zeros in first row or column carefully.

Watch out for greedy zeroing and indexing mistakes; use two-pass marking and zeroing.

Optimize your solution to O(m*n) time and O(1) space using first row and column as flags.

t1_01basic

Input[[1,1,1],[1,0,1],[1,1,1]]

Expected[[1,0,1],[0,0,0],[1,0,1]]

⏱ Performance - must finish in 2000ms

The zero at position (1,1) causes row 1 and column 1 to be zeroed.

💡 Think about marking rows and columns that contain zeros before modifying the matrix.

💡 Use the first row and first column as flags to avoid extra space.

💡 First pass: mark zeros in first row/column; second pass: zero out cells based on flags.

Why it failed: Failed basic case: likely did not mark rows and columns correctly or overwrote flags prematurely. Fix by using first row and column as flags and updating matrix in two passes.

✓ Correctly handled the canonical example with proper in-place zeroing.

t1_02basic

Input[[0,2,3],[4,5,6],[7,8,9]]

Expected[[0,0,0],[0,5,6],[0,8,9]]

⏱ Performance - must finish in 2000ms

Zero at (0,0) causes first row and first column to be zeroed.

💡 Check how zeros in the first row and column affect the entire row and column.

💡 Remember to separately track if first row and first column originally had zeros.

💡 Use boolean flags for first row and first column to avoid overwriting during marking.

Why it failed: Failed to handle zeros in first row or column correctly; flags overwritten too early. Fix by storing separate booleans for first row and column zero presence.

✓ Properly handled zeros in first row and column with correct flag usage.

t2_01edge

Input[[1,2,3],[4,5,6],[7,8,9]]

Expected[[1,2,3],[4,5,6],[7,8,9]]

⏱ Performance - must finish in 2000ms

Matrix with no zeros remains unchanged.

💡 If no zeros are found, the matrix should remain the same.

💡 Check that your code does not zero rows or columns unnecessarily.

💡 Ensure marking phase correctly detects absence of zeros before modification.

Why it failed: Incorrectly zeroed matrix with no zeros present; likely marking all rows/columns or not checking zero presence. Fix by only zeroing rows/columns marked during scanning.

✓ Correctly left matrix unchanged when no zeros present.

t2_02edge

Input[[0]]

Expected[[0]]

⏱ Performance - must finish in 2000ms

Single element matrix with zero remains zero.

💡 Test smallest matrix size with zero element.

💡 Ensure code handles single row and column without index errors.

💡 Mark and zero logic should work even for 1x1 matrix.

Why it failed: Failed single element zero matrix; likely index error or incorrect flag handling. Fix by handling single element matrices explicitly or ensuring loops handle size 1.

✓ Correctly handled single element zero matrix.

t2_03edge

Input[[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Expected[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

⏱ Performance - must finish in 2000ms

Zeros in first row and last column cause zeroing of corresponding rows and columns.

💡 Check how multiple zeros in first row affect zeroing.

💡 Remember to track first row and column zero presence separately.

💡 Update matrix in two passes to avoid premature overwriting.

Why it failed: Incorrect zeroing when multiple zeros in first row; flags overwritten too early. Fix by using separate booleans for first row and column zero presence.

✓ Correctly handled multiple zeros in first row and last column.

t3_01corner

Input[[1,0,3],[4,5,6],[0,8,9]]

Expected[[0,0,0],[0,0,6],[0,0,0]]

⏱ Performance - must finish in 2000ms

Zeros in middle and first column cause zeroing of corresponding rows and columns.

💡 Beware of greedy approaches that zero rows/columns immediately upon finding zero.

💡 Use two-pass approach to mark first, then zero to avoid cascading errors.

💡 Store zero presence in first row and column separately to avoid overwriting flags.

Why it failed: Greedy zeroing on first zero found causes over-zeroing; fix by marking first then zeroing in separate passes. This is the greedy trap test.

✓ Correctly avoided greedy trap by using two-pass marking and zeroing.

t3_02corner

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

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

⏱ Performance - must finish in 2000ms

Zero in middle row causes zeroing of row and column only once, not multiple times.

💡 Avoid confusion between zeroing once vs multiple times (0/1 vs unbounded).

💡 Mark rows and columns once, then zero all affected cells.

💡 Do not zero cells multiple times or re-mark during zeroing phase.

Why it failed: Confused 0/1 zeroing with unbounded zeroing causing repeated zeroing or incorrect results. Fix by marking rows and columns once before zeroing. This is the 0/1 vs unbounded confusion test.

✓ Handled zeroing exactly once per row and column correctly.

t3_03corner

Input[[1,2,3,4],[5,0,7,8],[9,10,11,12],[13,14,15,0]]

Expected[[1,0,3,0],[0,0,0,0],[9,0,11,0],[0,0,0,0]]

⏱ Performance - must finish in 2000ms

Multiple zeros in different rows and columns test off-by-one errors in indexing.

💡 Check indexing carefully when marking and zeroing columns and rows.

💡 Ensure loops cover all rows and columns without off-by-one mistakes.

💡 Use consistent zero-based indexing and verify boundaries.

Why it failed: Off-by-one errors caused missing or extra zeroing in rows or columns. Fix by carefully indexing loops from 0 to m-1 and 0 to n-1. This is the off-by-one indexing test.

✓ Correctly handled indexing for multiple zeros in matrix.

t4_01performance

Input{"_description":"n=200 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix size 200x200 tests O(m*n) time complexity must complete within 2 seconds.

💡 Optimal solution uses O(1) extra space and O(m*n) time.

💡 Avoid nested loops with exponential complexity.

💡 Use first row and column as flags to mark zeros efficiently.

Why it failed: TLE due to exponential or higher than O(m*n) complexity. Fix by implementing two-pass O(m*n) solution using first row and column as flags.

✓ Solution runs within time limit using O(m*n) complexity.

Practice

1. You are given an n x n matrix representing an image. The task is to rotate the image by 90 degrees clockwise in-place, without using extra space. Which of the following approaches guarantees an optimal in-place solution with O(1) extra space and O(n²) time complexity?

easy

A. Perform a layer-by-layer rotation by swapping four elements at a time in-place for each layer of the matrix.

B. Apply a dynamic programming approach to store intermediate rotations and build the final rotated matrix.

C. Use a brute force approach by creating a new matrix and copying elements to their rotated positions.

D. Transpose the matrix and then reverse each column to achieve the rotation.

Solution

1. Step 1: Understand the problem constraints

   The problem requires rotating the matrix in-place with O(1) extra space and O(n²) time.

2. Step 2: Evaluate approaches

   Brute force uses extra space, DP is unrelated, and transposing then reversing columns rotates counterclockwise, not clockwise. Layer-by-layer four-way swaps correctly rotate clockwise in-place.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Layer-by-layer swaps rotate in-place with correct direction and complexity [OK]

Hint: Layer-by-layer four-way swaps rotate in-place clockwise [OK]

Common Mistakes:

• Confusing transpose+reverse columns with clockwise rotation
• Using extra space when in-place is required

2. You need to fill an n x n matrix with numbers from 1 to n² in a pattern that starts at the top-left corner and proceeds in a clockwise spiral moving outward. Which approach guarantees filling all cells correctly without revisiting or skipping any cell?

easy

A. Greedy approach filling rows and columns independently without tracking boundaries

B. Dynamic programming to store partial sums and fill matrix based on subproblems

C. Directional simulation with boundary shrinking and cycling through directions

D. Sorting all numbers and placing them diagonally from top-left to bottom-right

Solution

1. Step 1: Understand the problem constraints

   The matrix must be filled in a spiral order, visiting each cell exactly once in a clockwise manner.

2. Step 2: Identify the approach that tracks boundaries and direction

   Directional simulation with boundary shrinking ensures that after filling one side, boundaries are updated to avoid revisiting cells, and directions cycle through right, down, left, and up correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary shrinking prevents overwriting and ensures full coverage [OK]

Hint: Track boundaries and directions to avoid revisits [OK]

Common Mistakes:

• Assuming greedy row/column fills without boundary checks works
• Confusing DP with spiral traversal
• Ignoring direction cycling leads to incomplete fills

3. Consider the following Python code snippet for validating a Sudoku board using bitmasking:

def isValidSudoku(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue
            val = ord(board[i][j]) - ord('1')
            mask = 1 << val
            box_index = (i // 3) * 3 + (j // 3)
            if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
                return false
            rows[i] |= mask
            cols[j] |= mask
            boxes[box_index] |= mask
    return true

board = [
    ['5','3','.','.','7','.','.','.','.'],
    ['6','.','.','1','9','5','.','.','.'],
    ['.','9','8','.','.','.','.','6','.'],
    ['8','.','.','.','6','.','.','.','3'],
    ['4','.','.','8','.','3','.','.','1'],
    ['7','.','.','.','2','.','.','.','6'],
    ['.','6','.','.','.','.','2','8','.'],
    ['.','.','.','4','1','9','.','.','5'],
    ['.','.','.','.','8','.','.','7','9']
]

print(isValidSudoku(board))

What is the output of this code?

easy

A. true

B. false

C. Raises an exception due to invalid indexing

D. Returns null

Solution

1. Step 1: Trace first few iterations

   All digits are unique in their rows, columns, and boxes; no mask conflicts occur.

2. Step 2: Confirm no duplicates found

   Since no duplicates are detected, the function completes and returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard valid Sudoku board returns true [OK]

Hint: No duplicates -> function returns true [OK]

Common Mistakes:

• Misreading box index calculation
• Assuming '.' causes errors
• Confusing return values

4. What is the time complexity of the optimal in-place Game of Life solution that encodes states using 4 integer values, given an m x n board?

medium

A. O(m + n) since only rows and columns are scanned

B. O(m * n * 8 * 2) due to checking neighbors twice

C. O(m * n * m * n) because each cell checks all other cells as neighbors

D. O(m * n) because each cell and its neighbors are processed in constant time

Solution

1. Step 1: Identify loops and operations

   Outer loops iterate over all m*n cells. For each cell, 8 neighbors are checked in constant time.

2. Step 2: Calculate total operations

   Total operations = m*n*8 = O(m*n), since 8 is constant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Neighbor checks are constant per cell -> linear in board size [OK]

Hint: Neighbor checks are constant per cell, so linear overall [OK]

Common Mistakes:

• Mistaking neighbor checks as nested loops over entire board
• Counting neighbor checks twice incorrectly
• Confusing linear scan with quadratic complexity

5. Examine the following buggy code snippet for Sudoku validation using bitmasking:

def isValidSudoku(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                continue
            val = ord(board[i][j]) - ord('1')
            mask = 1 << val
            box_index = i // 3 + (j // 3) * 3
            if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
                return false
            rows[i] |= mask
            cols[j] |= mask
            boxes[box_index] |= mask
    return true

What is the bug in this code?

medium

A. The rows and cols arrays should be initialized with sets, not integers.

B. The mask calculation is wrong; it should be 1 << (val + 1).

C. The code incorrectly includes '.' in the bitmask checks.

D. The box_index calculation is incorrect; it should be (i // 3) * 3 + (j // 3).

Solution

1. Step 1: Analyze box_index calculation

   The code uses box_index = i // 3 + (j // 3) * 3, which swaps row and column grouping.

2. Step 2: Correct formula for box_index

   The correct formula is (i // 3) * 3 + (j // 3) to map 3x3 boxes properly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect box_index causes missed duplicates in boxes [OK]

Hint: Box index formula must map 3x3 boxes correctly [OK]

Common Mistakes:

• Swapping row and column in box index
• Misusing bitmask shifts
• Including '.' in checks