Problem Overview

  • We are given a matrix of size m * n.
  • If any element in the matrix is 0, set its entire row and column to 0.
  • Constraint:
    • The solution must use O(1) extra space.

LeetCode - Set Matrix Zeroes

Example

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

Visual explanation of the transformation of the matrix

Brute Force

Intuition and Approach

  • Use an unordered_map to store positions of original zeros.

  • In a second traversal:

    • If a cell was originally zero, set its entire row and column to zero.
class Solution {
public:
  void setZeroes(vector<vector<int>>& matrix) {

      int m = matrix.size();
      int n = matrix[0].size();

      bool firstRowZero = false;
      bool firstColZero = false;

      // Check first row
      for (int j = 0; j < n; j++) {
          if (matrix[0][j] == 0)
              firstRowZero = true;
      }

      // Check first column
      for (int i = 0; i < m; i++) {
          if (matrix[i][0] == 0)
              firstColZero = true;
      }

      // Mark rows and columns
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {

              if (matrix[i][j] == 0) {
                  matrix[0][j] = 0;
                  matrix[i][0] = 0;
              }
          }
      }

      // Set rows to zero
      for (int i = 1; i < m; i++) {
          if (matrix[i][0] == 0) {
              for (int j = 1; j < n; j++) {
                  matrix[i][j] = 0;
              }
          }
      }

      // Set columns to zero
      for (int j = 1; j < n; j++) {
          if (matrix[0][j] == 0) {
              for (int i = 1; i < m; i++) {
                  matrix[i][j] = 0;
              }
          }
      }

      // Handle first row if first row contains zero
      if (firstRowZero) {
          for (int j = 0; j < n; j++) {
              matrix[0][j] = 0;
          }
      }

      // Handle first column if first column contains zero
      if (firstColZero) {
          for (int i = 0; i < m; i++) {
              matrix[i][0] = 0;
          }
      }
  }
};

Why It Fails

  • Extra space used is proportional to the number of zeros.
  • In the worst case, we store almost m * n positions using O(m*n) space.

Time and Space Complexity

  • Time: O(m * n)
  • Space: O(m * n)

In-Place Optimal Solution

The trick is to use the first row and first column as markers instead of extra space.

Intuition and Approach

  • Check if the first row contains zero.

  • Check if the first column contains zero.

  • Traverse the matrix from (1,1) to (m-1,n-1):

    • If matrix[i][j] == 0
      • Mark matrix[0][j] = 0
      • Mark matrix[i][0] = 0

  • Traverse rows again:

    • If first element of row is zero, set the entire row to zero.

  • Traverse columns again:

    • If first element of column is zero, set the entire column to zero.

  • Finally, handle the first row and first column separately.

Edge Case

  • First row and first column are used as markers.
  • If they originally contained zero, we must remember that using two boolean flags else we loose that data in the process.

Code Implementation

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        int n = matrix[0].size();

        bool firstRowZero = false;
        bool firstColZero = false;

        // Check first row
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0)
                firstRowZero = true;
        }

        // Check first column
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0)
                firstColZero = true;
        }

        // Mark rows and columns
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        // Set rows to zero
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Set columns to zero
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Handle first row if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Handle first column if needed
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

Time and Space Complexity

  • Time: O(m * n)
  • Space: O(1)

Final Takeaways

  • The first row and first column can act as storage.
  • Edge cases matter — especially when the storage area itself contains 0 data.