Zero Striping

The Matrix Infection problem requires modifying a matrix such that if any cell contains a specific value, its entire row and column are updated with that value. This tests understanding of in-place modifications and efficient matrix traversal.

matrixhash setsin-placetwo-passdata structures

Problem Statement

Given a two-dimensional integer matrix, if any element in the matrix is equal to a specified 'infection' value, modify the matrix such that all elements in the infected element's row and column are also set to the 'infection' value. This should be done in-place, meaning you should modify the original matrix directly without creating a new matrix.

Example 1

Input: matrix = [[3, 5, 0, 2], [8, 1, 9, 4], [6, 7, 2, 1], [9, 2, 5, 0]], infection_value = 0

Output: [[0, 0, 0, 0], [8, 1, 0, 4], [6, 7, 0, 1], [0, 0, 0, 0]]

The original matrix contains 0 at (0, 2) and (3, 3). Thus, row 0 and column 2, and row 3 and column 3 are set to 0.

Example 2

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], infection_value = 5

Output: [[1, 2, 3], [5, 5, 5], [7, 8, 9]]

The element 5 is at position (1,1). So, row 1 and column 1 are set to 5.

Constraints

-m == matrix.length
-n == matrix[i].length
-1 <= m, n <= 200
--100 <= matrix[i][j] <= 100
-The infection_value will be within the range of values in the matrix.

Brute Force Approach

The simplest approach is to first iterate through the matrix to identify all infected cells (cells containing the infection value). Then, for each infected cell, iterate through its row and column, setting all elements to the infection value. This is like finding all houses with a disease and then going house-to-house in the same street and avenue to spread the disease further.

TimeO(m * n * (m + n))

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem