Scale Engineer

Set Matrix Zeroes

Med
#0073Time: O((m*n) * (m+n))Space: O(m*n)20 companies
Data structures
ArrayHash TableMatrix
Companies
AdobeAmazonAppleBloomberg

Prompt

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
  • -231 <= matrix[i][j] <= 231 - 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?

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to use an auxiliary matrix of the same dimensions as the original. We can iterate through the original matrix to find the locations of all the zeros. Then, based on these locations, we modify the auxiliary matrix by setting the corresponding rows and columns to zero. Finally, we copy the contents of the auxiliary matrix back to the original one. This approach is simple to conceptualize but highly inefficient in terms of space.

Algorithm

  • Create a new matrix ans of size m x n and copy the original matrix into it.
  • Iterate through the original matrix from (i, j) = (0, 0) to (m-1, n-1).
  • If matrix[i][j] is 0:
    • Set all elements in row i of the ans matrix to 0.
    • Set all elements in column j of the ans matrix to 0.
  • After the iteration is complete, copy the ans matrix back to the original matrix.

Walkthrough

This method avoids the problem of modifying the matrix while iterating over it, which could lead to a chain reaction of zeroing out unintended rows and columns. By using a separate copy, we can safely record all the required changes before applying them.

Here's the breakdown:

  1. Create a new matrix, let's call it ans, with the same dimensions m x n and copy all elements from the original matrix into it.
  2. Iterate through the original matrix using nested loops for row i and column j.
  3. If you find an element matrix[i][j] that is 0, you then perform two more loops to set the entire i-th row and j-th column of the ans matrix to 0.
  4. After the initial iteration over the original matrix is complete, the ans matrix holds the desired final state. The last step is to copy the ans matrix back into the original matrix to satisfy the in-place requirement.
class Solution {    public void setZeroes(int[][] matrix) {        int m = matrix.length;        int n = matrix[0].length;        int[][] ans = new int[m][n];         // Create a copy of the original matrix        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                ans[i][j] = matrix[i][j];            }        }         // Iterate through the original matrix to find zeros        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (matrix[i][j] == 0) {                    // Set the entire row in the 'ans' matrix to 0                    for (int k = 0; k < n; k++) {                        ans[i][k] = 0;                    }                    // Set the entire column in the 'ans' matrix to 0                    for (int k = 0; k < m; k++) {                        ans[k][j] = 0;                    }                }            }        }         // Copy the 'ans' matrix back to the original matrix        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                matrix[i][j] = ans[i][j];            }        }    }}

Complexity

Time

O((m*n) * (m+n))

Space

O(m*n)

Trade-offs

Pros

  • Very simple and easy to understand.

  • Separates the logic of finding zeros from modifying the matrix, avoiding common pitfalls.

Cons

  • Extremely high space complexity, making it impractical for large matrices.

  • Inefficient time complexity, especially for matrices with many zeros.

Solutions

public class Solution {    public void SetZeroes(int[][] matrix) {        int m = matrix.Length, n = matrix[0].Length;        bool i0 = matrix[0].Contains(0), j0 = false;        for (int i = 0; i < m; ++i) {            if (matrix[i][0] == 0) {                j0 = 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 (i0) {            for (int j = 0; j < n; ++j) {                matrix[0][j] = 0;            }        }        if (j0) {            for (int i = 0; i < m; ++i) {                matrix[i][0] = 0;            }        }    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem