73. Set Matrix Zeroes

Set Matrix Zeroes (LeetCode 73) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Set Matrix Zeroes (In-place Marking) subpattern.

• Blind 75 · #70 of 75 · Math & Geometry
• NeetCode 150 · #138 of 150 · Math & Geometry
• NeetCode 250 · #234 of 250 · Math & Geometry

How to solve Set Matrix Zeroes

Set Matrix Zeroes is a Set Matrix Zeroes In-Place problem, part of Array/Matrix Manipulation Patterns. Learn the in-place marking technique to set entire rows and columns to zero efficiently without extra space.

Work towards the solution in these steps:

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.
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.
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.

The reference solution runs in O(m * n) time and O(1) space.

The Set Matrix Zeroes solution and editorial walks through the full approach with reference code.

Problem statement

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?

Topics and companies

Topics: Array, Hash Table, Matrix.

Reported in interviews at Facebook, Microsoft, Oracle, Amazon, Expedia, Bloomberg, Goldman Sachs, Apple.

How to practise Set Matrix Zeroes on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(1) space.

Open Set Matrix Zeroes in the code editor, or read the Set Matrix Zeroes editorial for a worked solution with its approach and complexity analysis.

Where Set Matrix Zeroes sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• Set Matrix Zeroes (In-place Marking) subpattern
• The full DSA patterns sheet

Problems related to Set Matrix Zeroes

Other problems that use the same Set Matrix Zeroes (In-place Marking) and Array/Matrix Manipulation Patterns techniques:

• Diagonal Traverse — Medium, same subpattern
• Game of Life — Medium, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Concatenation of Array — Easy, same pattern
• Contains Duplicate — Easy, same pattern

Set Matrix Zeroes FAQ