The popular answer (using the first row and col to record) is actually defective.


  • 0
    B

    Could anyone explain why this is AC??

    If the first row and first column don't have 0 originally. During the traversal of marking positions, they are actually modified. But those positions cannot later be reverted back.

    Thanks in advance as any help is appreciated.


  • 0

    Firstly, you need to traverse the first row and the first col to record whether they should be set to zeros at the end. (This only use two flag variable.so constant space).

    Then you go over the remaining grid, if there's zero, you set the specific marker to zero in first row and first column. (They should be set to zero no matter what).

    Then you use the marker to set the whole picture except for first row and first column.

    The final step is to use the two flags at the beginning to decide wether to set the first row and first column.


  • 0
    B

    Thank you for your answer. I understand the algorithm. My question is what happened to the first row and column if they don't need to be modified? Aren't we supposed to keep them untouched? But this solution change some of them to 0.


  • 0

    Some elements should be set to zeroes. See we have matrix[2][3]==0, [0][3] and [2][0] are supposed to be zero. They are just being set to zero before other elements in the same row or column while they are working as markers


  • 0
    B

    Oh!!! Thank you for your reply! I get it now.


Log in to reply
 

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