Bricks Falling When Hit


  • 0

    Click here to see the full article post


  • 0

    If there are two or more erasures hit same index, the answer may be wrong.


  • 0
    B

    The time complexity is O((N+Q)*α(N)), isn't it?


  • 0
    I

    What is the result of this test case?
    [[1],[1],[1],[1]]
    [[1,0],[1,0]]
    Why is the expected answer = [0, 0]?


  • 0

    @ibmtp380 Queries with repeated values are not allowed. This was not clearly explained in the problem, so I updated the explanation.

    The solution can be amended easily to work with repeated queries: all subsequent repeated queries are ignored and given an answer of zero.


  • 0
    T

    " or at least one of its (4-way) adjacent bricks will not drop"
    May we can use the algorithm -"flood fill" from the top Bricks
    answer=Bricks that are not stained
    it looks more simple......


  • 0
    N

    The question is not clear. For example:
    grid = [[1,0,0,0],[1,1,1,0]]
    hits = [[1,0]]
    Then after erase the brick at [1,0], the grid will become as
    grid = [[1,0,0,0],
    [0,1,1,0]]
    And "or at least one of its (4-way) adjacent bricks will not drop"
    therefore, the brick at [1,1] depends on the brick at [1,2], and vice versa.
    So if the brick at [1,1] drops, then brick at [1,2] have to be dropped because there is no one adjacent brick will not drop.
    But the question here is why the brick at [1,1] will drop? Doesn't it depend on whether the brick at [1,2] drops?
    BUT BUT BUT we do not know whether the brick at [1,2] drops yet.


  • 0
    T

    @nan0445 i think that...
    after hits
    first we set all brick will drops.
    then we use the rules:
    1 A brick will not drop if and only if it is directly connected to the top of the grid
    2 at least one of its (4-way) adjacent bricks will not drop
    then a part of bricks will not drop~~

    the rules remind me of the "flood fill"........ it looks like so simple......


  • 0

    It seems to me a dropped brick may hit another brick below.


  • 0

    For example, grid = [
    [0,1,0,1],
    [0,1,0,1],
    [0,0,0,1],
    [0,1,1,1]]. When we hit at [0,1], brick at [1,1] will drop and may be placed at [2,1].


  • 0
    M

    for grid . {{1, 0, 0, 0}, {0, 0, 0, 0} , {1, 1, 1, 0}} and only hit {{2, 0}} why is the answer 0 and not 2 . ?


  • 0
    M

    nevermind , realized that the top/wall is required to sustain any brick in first place so this is not a valid test case.


  • 0
    G

    Looks like rank array is redundant. I removed it and still my submission is accepted with better latency.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.