TIC
The Interns Company

Set Matrix Zeroes

MediumAcceptance: 48.5%
ArrayHash TableMatrix

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.

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

Input Format:

  • An m x n integer matrix

Output Format:

  • Modify the matrix in-place

Examples:

Example 1:

Input:

matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output:

[[1,0,1],[0,0,0],[1,0,1]]

Explanation:

The 0 is at position (1,1), so the entire second row and second column are set to 0.

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

Explanation:

The zeros are at positions (0,0) and (0,3), so the entire first and fourth columns and the first row are set to 0.

Solutions

O(1) Space Approach

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

Use the first row and first column as markers to indicate which rows and columns should be zeroed. Handle the first row and column separately.

Using Additional Arrays

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

Use two arrays to track which rows and columns need to be zeroed.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Check first row: No zeroes, so firstRowHasZero = false
  2. Check first column: No zeroes, so firstColHasZero = false
  3. Identify zeroes in rest of matrix: (1,1) is 0, so mark matrix[1][0] = 0 and matrix[0][1] = 0
  4. Process rows: row 1 has marker (matrix[1][0] = 0), so zero out entire row 1
  5. Process columns: column 1 has marker (matrix[0][1] = 0), so zero out entire column 1
  6. First row and first column don't need zeroing
  7. Result: [[1,0,1],[0,0,0],[1,0,1]]

Hints

Hint 1
A simple solution would be to use a separate matrix to track which rows and columns should be set to zero, but can you do it with O(1) extra space?
Hint 2
You can use the first row and first column of the input matrix itself to track which rows and columns should be zeroed.
Hint 3
Be careful about handling the first row and first column themselves if they contain zeros.

Video Tutorial

Set Matrix Zeroes - O(1) Space Solution

YouTube•Learn the Set Matrix Zeroes solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize how the matrix is transformed when zeros are propagated to their corresponding rows and columns.

Key visualization elements:

  • zero positions
  • affected rows
  • affected columns

Similar Questions

Number of Islands

Medium

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Rotate Image

Medium

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Asked By

AmazonMicrosoftFacebookGoogleAppleAdobeBloomberg

Implementation Notes

This problem tests understanding of matrix operations and in-place modifications. The key insight is to use the first row and column as markers to minimize space usage.