Set Matrix Zeroes

🎯

Set Matrix Zeroes

mediumMATRIXAmazonMicrosoftFacebook

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.

💡 This problem is about modifying a matrix in-place based on certain conditions. Beginners often struggle because they try to use extra space or overwrite data prematurely, losing information needed for later steps.

📋

Problem Statement

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

💡

Example

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

Output[[1,0,1],[0,0,0],[1,0,1]]

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

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

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

Zeros at (0,0) and (0,3) cause first row and first column and last column to be zeroed.

• Matrix with no zeros → matrix remains unchanged
• Matrix with all zeros → matrix remains all zeros
• Matrix with zeros only in first row or first column → ensure flags do not overwrite prematurely
• Matrix with single row or single column → handle edge dimension cases

⚠️

Common Mistakes

Overwriting first row or column before saving zero info

Incorrect zeroing of rows or columns, missing some zeros

✅ Use separate booleans to track if first row or column originally had zeros before marking

Zeroing rows and columns during first pass

Premature zeroing causes loss of information about other zeros

✅ Separate detection and update phases clearly

Not handling single row or single column matrices

Index errors or incorrect zeroing

✅ Add checks or handle these edge cases explicitly

Using extra space arrays but forgetting to initialize them correctly

Incorrect zeroing or runtime errors

✅ Initialize boolean arrays or sets properly before use

Confusing row and column indices when marking zeros

Wrong rows or columns zeroed

✅ Carefully track and test row vs column indices

🧠

Brute Force (Mark and Update with Extra Matrix)

💡 This approach uses extra space to mark which rows and columns should be zeroed. It is straightforward and helps beginners understand the problem without worrying about in-place constraints.

Intuition

Scan the matrix to find zeros and record their row and column indices. Then, zero out all recorded rows and columns in a separate pass.

Algorithm

1. Create two boolean arrays to track which rows and columns contain zeros.
2. Traverse the matrix to mark rows and columns that have zeros.
3. Traverse the matrix again, setting elements to zero if their row or column is marked.
4. Return the modified matrix.

💡 Separating detection and update phases avoids premature overwriting, which is a common beginner pitfall.

</>

Code

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    rows = [False] * m
    cols = [False] * n
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                rows[i] = True
                cols[j] = True
    for i in range(m):
        for j in range(n):
            if rows[i] or cols[j]:
                matrix[i][j] = 0

# Example usage
if __name__ == '__main__':
    mat = [[1,1,1],[1,0,1],[1,1,1]]
    setZeroes(mat)
    print(mat)

Line Notes

m, n = len(matrix), len(matrix[0])Determine matrix dimensions for iteration limits

rows = [False] * mInitialize row markers to track zero presence

cols = [False] * nInitialize column markers to track zero presence

if matrix[i][j] == 0:Detect zero elements to mark their row and column

if rows[i] or cols[j]:Set element to zero if its row or column was marked

import java.util.*;
public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] rows = new boolean[m];
        boolean[] cols = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {{1,1,1},{1,0,1},{1,1,1}};
        sol.setZeroes(mat);
        System.out.println(Arrays.deepToString(mat));
    }
}

Line Notes

int m = matrix.length, n = matrix[0].length;Get matrix dimensions for loops

boolean[] rows = new boolean[m];Track rows containing zeros

boolean[] cols = new boolean[n];Track columns containing zeros

if (matrix[i][j] == 0)Identify zero elements to mark rows and columns

if (rows[i] || cols[j])Zero out elements in marked rows or columns

#include <iostream>
#include <vector>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<bool> rows(m, false), cols(n, false);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                rows[i] = true;
                cols[j] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (rows[i] || cols[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

int main() {
    vector<vector<int>> mat = {{1,1,1},{1,0,1},{1,1,1}};
    setZeroes(mat);
    for (auto &row : mat) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int m = matrix.size(), n = matrix[0].size();Capture matrix dimensions for iteration

vector<bool> rows(m, false), cols(n, false);Boolean vectors to mark zero rows and columns

if (matrix[i][j] == 0)Detect zero elements to mark their row and column

if (rows[i] || cols[j])Set matrix element to zero if row or column marked

function setZeroes(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const rows = new Array(m).fill(false);
    const cols = new Array(n).fill(false);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                rows[i] = true;
                cols[j] = true;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (rows[i] || cols[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

// Example usage
const mat = [[1,1,1],[1,0,1],[1,1,1]];
setZeroes(mat);
console.log(mat);

Line Notes

const m = matrix.length, n = matrix[0].length;Get matrix dimensions for loops

const rows = new Array(m).fill(false);Initialize row flags for zeros

const cols = new Array(n).fill(false);Initialize column flags for zeros

if (matrix[i][j] === 0)Detect zero elements to mark rows and columns

if (rows[i] || cols[j])Zero out elements in marked rows or columns

⏱

Complexity

TimeO(m*n)

SpaceO(m + n)

We scan the matrix twice, each O(m*n). Extra space is used for two arrays of size m and n.

💡 For a 200x200 matrix, this means about 80,000 operations and 400 extra booleans, which is manageable but not optimal.

Interview Verdict: Accepted

This approach is accepted but uses extra space, so it is a good starting point but not the final optimized solution.

🧠

Optimal In-Place Using First Row and Column as Flags

💡 This approach cleverly uses the first row and first column of the matrix itself to store flags, eliminating extra space usage beyond two booleans. Beginners learn how to reuse input space safely.

Intuition

Use the first row and first column to mark which rows and columns should be zeroed, then update the matrix in a second pass. Use two separate booleans to track if the first row and first column originally had zeros.

Algorithm

1. Check if first row has any zeros and store in a boolean.
2. Check if first column has any zeros and store in a boolean.
3. Use first row and column to mark zeros for other rows and columns.
4. Zero out cells based on marks in first row and column.
5. Finally, zero out first row and/or first column if needed.

💡 The tricky part is preserving the original first row and column zero info before overwriting them as flags.

</>

Code

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

# Example usage
if __name__ == '__main__':
    mat = [[1,1,1],[1,0,1],[1,1,1]]
    setZeroes(mat)
    print(mat)

Line Notes

first_row_zero = any(matrix[0][j] == 0 for j in range(n))Check if first row contains zero before using it as flag storage

first_col_zero = any(matrix[i][0] == 0 for i in range(m))Check if first column contains zero before using it as flag storage

if matrix[i][j] == 0:Mark corresponding first row and column positions as zero flags

if matrix[i][0] == 0 or matrix[0][j] == 0:Use flags to zero out cells

if first_row_zero:Zero out first row if originally contained zero

if first_col_zero:Zero out first column if originally contained zero

public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {{1,1,1},{1,0,1},{1,1,1}};
        sol.setZeroes(mat);
        System.out.println(java.util.Arrays.deepToString(mat));
    }
}

Line Notes

boolean firstRowZero = false, firstColZero = false;Track if first row or column originally had zeros

for (int j = 0; j < n; j++)Scan first row for zeros before using it as flag storage

for (int i = 0; i < m; i++)Scan first column for zeros before using it as flag storage

if (matrix[i][j] == 0)Mark first row and column to flag zero rows and columns

if (matrix[i][0] == 0 || matrix[0][j] == 0)Zero out cells based on flags

if (firstRowZero)Zero out first row if needed

if (firstColZero)Zero out first column if needed

#include <iostream>
#include <vector>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if (firstRowZero) {
        for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

int main() {
    vector<vector<int>> mat = {{1,1,1},{1,0,1},{1,1,1}};
    setZeroes(mat);
    for (auto &row : mat) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

bool firstRowZero = false, firstColZero = false;Booleans to remember if first row/column had zeros originally

for (int j = 0; j < n; j++)Check first row for zeros before using it as flag storage

for (int i = 0; i < m; i++)Check first column for zeros before using it as flag storage

if (matrix[i][j] == 0)Mark first row and column to indicate zero rows and columns

if (matrix[i][0] == 0 || matrix[0][j] == 0)Zero out cells based on flags

if (firstRowZero)Zero out first row if needed

if (firstColZero)Zero out first column if needed

function setZeroes(matrix) {
    const m = matrix.length, n = matrix[0].length;
    let firstRowZero = false, firstColZero = false;
    for (let j = 0; j < n; j++) {
        if (matrix[0][j] === 0) {
            firstRowZero = true;
            break;
        }
    }
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            firstColZero = true;
            break;
        }
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if (firstRowZero) {
        for (let j = 0; j < n; j++) matrix[0][j] = 0;
    }
    if (firstColZero) {
        for (let i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

// Example usage
const mat = [[1,1,1],[1,0,1],[1,1,1]];
setZeroes(mat);
console.log(mat);

Line Notes

let firstRowZero = false, firstColZero = false;Track if first row or column originally had zeros

for (let j = 0; j < n; j++)Scan first row for zeros before using it as flag storage

for (let i = 0; i < m; i++)Scan first column for zeros before using it as flag storage

if (matrix[i][j] === 0)Mark first row and column to flag zero rows and columns

if (matrix[i][0] === 0 || matrix[0][j] === 0)Zero out cells based on flags

if (firstRowZero)Zero out first row if needed

if (firstColZero)Zero out first column if needed

⏱

Complexity

TimeO(m*n)

SpaceO(1)

We scan the matrix a few times but only use constant extra space for two booleans.

💡 For a 200x200 matrix, this is about 80,000 operations but no extra arrays, making it space efficient.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its optimal space usage and clarity once understood.

🧠

Alternative: Using Sets to Track Rows and Columns

💡 This approach uses sets to track rows and columns with zeros. It is simpler than arrays for some languages and helps understand the marking concept before optimizing space.

Intuition

Traverse the matrix once to add zero-containing rows and columns to sets, then zero out those rows and columns in a second pass.

Algorithm

1. Initialize empty sets for rows and columns.
2. Traverse the matrix to add indices of zero elements to these sets.
3. Traverse the matrix again, zeroing elements if their row or column is in the sets.
4. Return the modified matrix.

💡 Using sets avoids manual boolean array management and duplicates, making the logic clearer.

</>

Code

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_rows = set()
    zero_cols = set()
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_rows.add(i)
                zero_cols.add(j)
    for i in range(m):
        for j in range(n):
            if i in zero_rows or j in zero_cols:
                matrix[i][j] = 0

# Example usage
if __name__ == '__main__':
    mat = [[1,1,1],[1,0,1],[1,1,1]]
    setZeroes(mat)
    print(mat)

Line Notes

zero_rows = set()Initialize set to track rows with zeros

zero_cols = set()Initialize set to track columns with zeros

if matrix[i][j] == 0:Add row and column indices to sets when zero found

if i in zero_rows or j in zero_cols:Zero out elements if their row or column is marked

import java.util.*;
public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Set<Integer> zeroRows = new HashSet<>();
        Set<Integer> zeroCols = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows.add(i);
                    zeroCols.add(j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (zeroRows.contains(i) || zeroCols.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {{1,1,1},{1,0,1},{1,1,1}};
        sol.setZeroes(mat);
        System.out.println(Arrays.deepToString(mat));
    }
}

Line Notes

Set<Integer> zeroRows = new HashSet<>();Use set to track rows with zeros

Set<Integer> zeroCols = new HashSet<>();Use set to track columns with zeros

if (matrix[i][j] == 0)Add row and column indices to sets when zero found

if (zeroRows.contains(i) || zeroCols.contains(j))Zero out elements if their row or column is marked

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    unordered_set<int> zeroRows, zeroCols;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                zeroRows.insert(i);
                zeroCols.insert(j);
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (zeroRows.count(i) || zeroCols.count(j)) {
                matrix[i][j] = 0;
            }
        }
    }
}

int main() {
    vector<vector<int>> mat = {{1,1,1},{1,0,1},{1,1,1}};
    setZeroes(mat);
    for (auto &row : mat) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

unordered_set<int> zeroRows, zeroCols;Sets to track rows and columns with zeros

if (matrix[i][j] == 0)Add row and column indices to sets when zero found

if (zeroRows.count(i) || zeroCols.count(j))Zero out elements if their row or column is marked

function setZeroes(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const zeroRows = new Set();
    const zeroCols = new Set();
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                zeroRows.add(i);
                zeroCols.add(j);
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (zeroRows.has(i) || zeroCols.has(j)) {
                matrix[i][j] = 0;
            }
        }
    }
}

// Example usage
const mat = [[1,1,1],[1,0,1],[1,1,1]];
setZeroes(mat);
console.log(mat);

Line Notes

const zeroRows = new Set();Set to track rows with zeros

const zeroCols = new Set();Set to track columns with zeros

if (matrix[i][j] === 0)Add row and column indices to sets when zero found

if (zeroRows.has(i) || zeroCols.has(j))Zero out elements if their row or column is marked

⏱

Complexity

TimeO(m*n)

SpaceO(m + n)

We scan the matrix twice and use sets that can grow up to size m and n.

💡 This approach is easier to implement but uses extra space proportional to matrix dimensions.

Interview Verdict: Accepted

This approach is acceptable but less space efficient than the in-place flag method.

📊

All Approaches - One-Glance Tradeoffs

💡 The in-place first row/column flag approach is best for interviews due to optimal space and clarity once understood.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Extra Boolean Arrays)	O(m*n)	O(m + n)	No	N/A	Good to mention as baseline, rarely coded fully
2. Optimal In-Place Using First Row and Column	O(m*n)	O(1)	No	N/A	Preferred approach to code in interviews
3. Using Sets to Track Rows and Columns	O(m*n)	O(m + n)	No	N/A	Simpler alternative, good for quick implementation

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach using extra space to mark rows and columns.Explain the space optimization using the first row and column as flags.Discuss alternative approaches if time permits.Code the optimal in-place solution carefully, testing edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to handle in-place modifications, edge cases like zeros in first row/column, and your understanding of space-time tradeoffs.

Common Follow-ups

• What if you cannot use the first row and column as flags? → Use extra space arrays or sets.
• How to handle very large matrices efficiently? → The in-place approach is already optimal in space.

💡 Follow-ups often test your understanding of space optimization and edge case handling.

🔍

Pattern Recognition

When to Use

1) You need to modify a matrix in-place; 2) Zero elements affect entire rows and columns; 3) Space optimization is required; 4) Two-pass marking and updating is possible.

Signature Phrases

set entire row and column to zeromodify matrix in-placeuse first row and column as flags

NOT This Pattern When

Problems that require only row-wise or column-wise operations without cross-effects are different.

Similar Problems

Game of Life - in-place matrix update with neighbor rulesRotate Image - in-place matrix rotationSpiral Matrix - matrix traversal pattern

Practice

1. Consider the following Python function that computes the sum of the diagonals of a square matrix:

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total -= mat[n//2][n//2]
    return total

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(diagonalSum(matrix))

What is the value of total after the loop completes but before the if-condition is applied?

easy

A. 15

B. 25

C. 30

D. 45

Solution

1. Step 1: Trace the loop iterations

   For i=0: total = 0 + mat[0][0] + mat[0][2] = 0 + 1 + 3 = 4 For i=1: total = 4 + mat[1][1] + mat[1][1] = 4 + 5 + 5 = 14 For i=2: total = 14 + mat[2][2] + mat[2][0] = 14 + 9 + 7 = 30

2. Step 2: Note that the if-condition has not yet been applied

   The total before subtracting the center element is 30.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of diagonals before center correction is 30 [OK]

Hint: Sum both diagonals first, then adjust center if needed [OK]

Common Mistakes:

• Forgetting to subtract center element once
• Double counting center element
• Off-by-one in indices

2. You are given a 9x9 grid partially filled with digits 1-9 and empty cells. You need to verify if the grid satisfies the constraints that each digit appears only once per row, column, and each of the nine 3x3 sub-boxes. Which algorithmic approach best guarantees an efficient and correct validation of this problem?

easy

A. Use a brute force approach checking each row, column, and box separately with nested loops and sets.

B. Use a single pass with hash sets to track digits seen in rows, columns, and boxes simultaneously.

C. Apply dynamic programming to store intermediate results of valid sub-grids and build up to the full grid.

D. Use a greedy approach by placing digits one by one and backtracking on conflicts.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking uniqueness of digits in rows, columns, and 3x3 boxes simultaneously.

2. Step 2: Evaluate approaches

   Brute force (A) works but is less efficient and involves multiple passes. DP (C) is not applicable as this is a validation, not an optimization problem. Greedy with backtracking (D) is for solving Sudoku, not validating. Single pass with hash sets (B) efficiently tracks all constraints in one iteration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with sets covers all constraints efficiently [OK]

Hint: Single pass with sets covers all constraints efficiently [OK]

Common Mistakes:

• Confusing validation with solving (greedy/backtracking)
• Thinking DP applies to validation
• Believing multiple passes are necessary

3. What is the time complexity of the optimal staircase search algorithm for counting negative numbers in an m x n sorted matrix, and why?

medium

A. O(m * n) because each element might be visited once.

B. O(n) because it only scans the top row and last column.

C. O(m log n) because it performs binary search on each row.

D. O(m + n) because the algorithm moves at most m times down and n times left.

Solution

1. Step 1: Analyze movement in matrix

   The algorithm starts at top-right and moves left or down, never revisiting cells.

2. Step 2: Count maximum moves

   Maximum moves down = m, maximum moves left = n, total moves ≤ m + n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear traversal along edges, not full matrix scan [OK]

Hint: Moves only left or down once per step, total ≤ m+n [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Assuming binary search per row
• Ignoring that each cell is visited once

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. The following code attempts to return the spiral order of a matrix. Which line contains a subtle bug that can cause repeated elements or index errors?

medium

A. Line where bottom row is traversed without checking if top <= bottom

B. Line where right is decremented after traversing the right column

C. Line where left column is traversed with boundary check

D. Line where top is incremented after traversing the top row

Solution

1. Step 1: Identify missing boundary check

   The code traverses the bottom row without verifying if top <= bottom, which can cause duplicates or index errors when boundaries cross.

2. Step 2: Confirm other lines are correct

   Top increment, right decrement, and left column traversal have proper boundary checks or are logically correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check before bottom row traversal causes subtle bugs [OK]

Hint: Check boundary conditions before each traversal [OK]

Common Mistakes:

• Forgetting boundary checks before bottom or left traversal
• Incorrectly updating boundaries causing infinite loops
• Misplaced increments/decrements