Set Matrix Zeroes

LeetCode 73 | Difficulty: Medium

Medium

Problem Description

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[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]]

Constraints:

- `m == matrix.length`

- `n == matrix[0].length`

- `1 <= m, n <= 200`

- `-2^31 <= matrix[i][j] <= 2^31 - 1`

Follow up:

- A straightforward solution using `O(mn)` space is probably a bad idea.

- A simple improvement uses `O(m + n)` space, but still not the best solution.

- Could you devise a constant space solution?

Topics: Array, Hash Table, Matrix

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 308 ms)

Metric	Value
Runtime	308 ms
Memory	N/A
Date	2018-03-23

Solution

public class Solution {
    public void SetZeroes(int[,] matrix) {
        int m = matrix.GetLength(0);
    int n = matrix.GetLength(1);
    HashSet<int> rows = new HashSet<int>();
    HashSet<int> cols = new HashSet<int>();
    
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(matrix[i,j]==0)
            {
                rows.Add(i);
                cols.Add(j);
                
            }
        }
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (rows.Contains(i) || cols.Contains(j))
            {
                matrix[i, j] = 0;
            }
        }
    }
    }
}

📜 1 more C# submission(s)

Submission (2018-03-23) — 608 ms, N/A

public class Solution {
    public void SetZeroes(int[,] matrix) {
        int m = matrix.GetLength(0);
    int n = matrix.GetLength(1);
    bool fr=false, fc=false;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(matrix[i,j]==0)
            {
                if(i==0) fr=true;
                if(j==0) fc=true;
                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(fr)
    {
        for (int j = 0; j < n; j++)
        {
            matrix[0,j] = 0;
        }
    }
    if(fc)
    {
        for (int i = 0; i < m; i++)
        {
            matrix[i,0] = 0;
        }
    }
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don't want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.

Hint 2: Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with O(1) space.

Hint 3: We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.

Hint 4: We can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero.