0085MediumArrayHash TableMatrix

Blank The Failed Sites

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A test bench records one signed offset per site of a panel into sheet, a grid of rows rows by cols columns. A site whose offset came out as exactly 0 failed its probe, and a failed probe throws doubt on every site sharing its row and every site sharing its column.

Write that doubt into the sheet. Once you are done, a site must hold 0 when it failed, when any site in its row failed, or when any site in its column failed. Every other site must still hold the offset it arrived with.

Failures are judged from the offsets as they were handed to you. A 0 you wrote yourself never counts as a failure and must not spread further.

The bench firmware has no room for a second panel of this size, so rewrite sheet in the storage it already occupies. Beyond a fixed handful of scratch values, no extra space may be used, however large rows and cols grow. Return sheet after marking it.

Examples

Example 1

Input: sheet = [[4, 0], [7, 9]]
Output: [[0, 0], [7, 0]]

The top right site failed, so the top row and the right column are blanked. The bottom left site keeps its offset because neither its row nor its column holds a failure.

Example 2

Input: sheet = [[3, 8, 5], [6, 0, 2], [9, 4, 7]]
Output: [[3, 0, 5], [0, 0, 0], [9, 0, 7]]

Only the middle site failed, which blanks the middle row and the middle column and leaves the four corners untouched.

Example 3

Input: sheet = [[0, 6], [5, 5]]
Output: [[0, 0], [0, 5]]

The failure sits in the first row and the first column, so both of them are blanked, and only the bottom right site survives.

Constraints

rows == sheet.length
cols == sheet[0].length
1 <= rows, cols <= 200
-2^31 <= sheet[r][c] <= 2^31 - 1
Only a fixed amount of extra space may be used; no second grid of size rows by cols

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def blank_failed_sites(sheet: list[list[int]]) -> list[list[int]]:

Java

public int[][] blankFailedSites(int[][] sheet)

The intended approach

Time O(rows * cols)Space O(1)

The sheet can carry its own bookkeeping: let site `sheet[r][0]` remember whether row `r` must be blanked and `sheet[0][c]` remember the same for column `c`. Those two strips overlap at the top left, so first note separately whether the top row and the left column each hold a failure, then mark the strips from the interior, blank the interior from the strips, and only then blank the two strips themselves. Two extra flags are the entire cost.

Pythonentry point: blank_failed_sites

def blank_failed_sites(sheet):
    rows = len(sheet)
    cols = len(sheet[0])
    top_failed = any(sheet[0][c] == 0 for c in range(cols))
    left_failed = any(sheet[r][0] == 0 for r in range(rows))
    for r in range(1, rows):
        for c in range(1, cols):
            if sheet[r][c] == 0:
                sheet[r][0] = 0
                sheet[0][c] = 0
    for r in range(1, rows):
        for c in range(1, cols):
            if sheet[r][0] == 0 or sheet[0][c] == 0:
                sheet[r][c] = 0
    if top_failed:
        for c in range(cols):
            sheet[0][c] = 0
    if left_failed:
        for r in range(rows):
            sheet[r][0] = 0
    return sheet

The obvious version

Ignore the space rule: collect the failing row indices and column indices into two sets from the untouched sheet, then build a fresh grid where a site is blank whenever its row or column is in one of those sets.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_blank_failed_sites(sheet):
    rows = len(sheet)
    cols = len(sheet[0])
    dead_rows = set()
    dead_cols = set()
    for r in range(rows):
        for c in range(cols):
            if sheet[r][c] == 0:
                dead_rows.add(r)
                dead_cols.add(c)
    marked = []
    for r in range(rows):
        row = []
        for c in range(cols):
            if r in dead_rows or c in dead_cols:
                row.append(0)
            else:
                row.append(sheet[r][c])
        marked.append(row)
    return marked

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in