:orphan:

Set Matrix Zeroes
=================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/set-matrix-zeroes/

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 <https://en.wikipedia.org/wiki/In-place_algorithm>`__.

 

**Example 1:**

|image1|

::


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

**Example 2:**

|image2|

::


   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``\ :sup:```31```\ ``<= matrix[i][j] <= 2``\ :sup:```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?

.. |image1| image:: https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg

.. highlight:: python

Pattern
-------
Array, Hash Table, Matrix

Solution
--------
We make 2 passes over  ``matrix``. In the first pass, we find all the indices
where ``matrix[i][j] == 0`` and store them in a list. In the second pass, we
zero all the rows and columns in the list of indices. We can make a small
optimization to convert the indices to a seet to avoid setting a row or column
to zero twice.

Code
----

.. literalinclude:: ../problems/medium/set-matrix-zeroes/set_matrix_zeroes__approach_1.py
    :language: python
    :lines: 13-

Test
----
>>> from set_matrix_zeroes__approach_1 import setZeroes
>>> matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
>>> setZeroes(matrix)
>>> matrix
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
>>> matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
>>> setZeroes(matrix)
>>> matrix
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

Complexity
----------
| :math:`m` is the number of rows and :math:`n` is the number of columns in the input matrix
| Time: :math:`O(m n)` — pass through matrix twice
| Auxiliary Space: :math:`O(m n)` — indices of zeros which is :math:`m n` in the worst case when all elements are zero

.. autofunction:: set_matrix_zeroes__approach_1.setZeroes