FastPrepSet Matrix Zeroes

Set Matrix Zeroes

Google logoGoogle● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

You are given a nonempty rectangular integer matrix matrix. If an element is 0, set every element in its row and column to 0.

Modify the matrix in place using O(1) auxiliary space, then return the same transformed matrix for comparison.

Only zeroes present in the original matrix determine which rows and columns become zero.

Interview follow-up

Be prepared to explain how to process a matrix too large to fit in memory by scanning storage-backed blocks. This external-memory variant is discussion-only; the judged function receives the in-memory matrix described above.

Function

setZeroes(matrix: int[][]) → int[][]

Examples

Example 1

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

The original zero at row 1, column 1 makes the middle row and middle column zero.

Example 2

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]return = [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

The original zeroes in the first row require that row and the first and fourth columns to become zero.

Constraints

  • 1 <= matrix.length <= 200.
  • 1 <= matrix[0].length <= 200.
  • Every row has the same number of columns.
  • -2^31 <= matrix[i][j] <= 2^31 - 1.
  • The algorithm must use O(1) auxiliary space for the judged in-memory matrix.

More Google problems

See Google hiring insights
public int[][] setZeroes(int[][] matrix) {
  // Write your code here.
}
matrix[[1,1,1],[1,0,1],[1,1,1]]
expected[[1,0,1],[0,0,0],[1,0,1]]
Checking account…