Bricks Falling When Hit

HardGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n binary grid where 1 is a brick and 0 is empty. A brick is **stable** if it is in the top row, or if it is 4-directionally adjacent to at least one other stable brick. You are also given a list of hits, applied in order. hits[i] = [row, col] erases the brick at that cell, if there is one; hitting an empty cell does nothing. After each erasure, every brick that is no longer stable falls and disappears from the grid at once. Fallen bricks do not land on anything. Return an array result where result[i] is the number of bricks that fell because of hit i. The erased brick itself does not count. All hit positions are distinct, and every brick in the starting grid is stable.

Examples

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Erasing (1,0) leaves (1,1) and (1,2) with no path to the top row, so both fall.
Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Erasing (1,1) drops nothing, since (1,0) still hangs from (0,0). Erasing (1,0) next also drops nothing.

Constraints

  • m == grid.length, n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j] is 0 or 1
  • 1 <= hits.length <= 4 * 10^4
  • hits[i] is inside the grid and all hits are distinct
  • Every brick in the initial grid is stable

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems