@meta
title: Set Matrix Zero
questionNo: 1
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
Given an m x n matrix, if any cell contains 0, set its complete row and complete column to 0.
Return the final matrix after applying all such updates.
In interviews, always clarify whether extra space is allowed or whether the matrix must be modified in-place.
@endsection

@section
region: left
title: Examples
content:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Explanation: Since matrix[1][1] is 0, row 1 and column 1 become 0.
---
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Explanation: Zeroes in row 0 force columns 0 and 3 to become 0 as well.
@endsection

@section
region: right
title: Custom Notes
content:
- Brute force teaches why direct zeroing is dangerous.
- Better approach is easiest to explain under pressure.
- Optimal approach reuses first row and first column as markers.
- Collision point is matrix[0][0], so keep a separate col0 flag for the first column.
- Memory hook: mark, scan, then zero from the markers.
@endsection

@section
region: full
title: Brute Force Approach: TC: O(m*n*(m+n)).   SC: O(1)
badge: 1 / 4
content:
Algorithm: Use a temporary marker value like -1 for cells that should later become 0.
Pseudo:
- Traverse every cell in the matrix.
- When matrix[i][j] == 0, mark all non-zero cells in row i as -1.
- Mark all non-zero cells in column j as -1.
- After the traversal, replace every -1 with 0.
Why mention it: It clearly shows why changing directly to 0 during the first pass creates accidental extra zeroes.
@endsection

@section
region: full
title: Better Approach : TC: O(m*n) SC: O(m+n)
badge: 2 / 4
content:
Algorithm: Store which rows and columns must become 0 in two helper arrays.
Pseudo:
- Create row[m] and col[n] initialized with 0.
- First pass: if matrix[i][j] == 0, set row[i] = 1 and col[j] = 1.
- Second pass: if row[i] == 1 or col[j] == 1, set matrix[i][j] = 0.
Interview line: This is the cleanest version when the interviewer does not insist on constant extra space.
@endsection

@section
region: full
title: Optimal Approach : TC: O(m*n).  SC: O(1)
badge: 3 / 4
content:
Algorithm: Use the first row and first column of the matrix itself as marker storage.
Pseudo:
- Keep a variable col0 = 1 to remember whether column 0 must become 0.
- First pass: when matrix[i][j] == 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.
- If j == 0, set col0 = 0 because the first column also needs zeroing.
- Second pass: iterate from bottom-right and zero matrix[i][j] when
   matrix[i][0] == 0 or matrix[0][j] == 0.
- At the end of each row, if col0 == 0 then set matrix[i][0] = 0.
Key insight: row 0 and col 0 become free marker arrays, while col0 solves the matrix[0][0] collision.
@endsection

@section
region: full
title: Optimal Approach : TC: O(m*n).  SC: O(1)
badge: 4 / 4
content:
Algorithm:Instead of using separate arrays, we use the first row and first column of the matrix itself to store whether a row or column needs to be zeroed. We also store one extra variable:
col0 → tells whether the first column should become zero.
    (We use this because matrix[0][0] is already shared by both first row and first
     column.)
Then:
First pass: Traverse the matrix and whenever a zero is found, mark its row and
  column by setting matrix[i][0] = 0 and matrix[0][j] = 0.
Second pass: Use those markers to set the required cells to zero.

Finally, handle the first column separately using col0.
This is the most space-efficient approach because we reuse the matrix itself as marker storage.
@endsection

@section
region: grid
title: PCode
badge: 1 / 4
codeLang: pseudo
content:
FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            mark all non-zero cells in row i as -1
            mark all non-zero cells in column j as -1

FOR each row i
    FOR each column j
        IF matrix[i][j] == -1
            matrix[i][j] = 0

RETURN matrix
@endsection

@section
region: grid
title: PCode
badge: 2 / 4
codeLang: pseudo
content:
rows = number of rows
cols = number of columns
row[0...rows-1] = 0
col[0...cols-1] = 0

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            row[i] = 1
            col[j] = 1

FOR each row i
    FOR each column j
        IF row[i] == 1 OR col[j] == 1
            matrix[i][j] = 0

RETURN matrix
@endsection

@section
region: grid
title: PCode
badge: 3 / 4
codeLang: pseudo
content:
rows = number of rows
cols = number of columns
col0 = 1

FOR each row i
    FOR each column j
        IF matrix[i][j] == 0
            matrix[i][0] = 0
            IF j != 0
                matrix[0][j] = 0
            ELSE
                col0 = 0

FOR i from rows - 1 down to 0
    FOR j from cols - 1 down to 1
        IF matrix[i][0] == 0 OR matrix[0][j] == 0
            matrix[i][j] = 0
    IF col0 == 0
        matrix[i][0] = 0

RETURN matrix
@endsection

@section
region: grid
title: PCode
badge: 4 / 4
codeLang: pseudo
content:
Initialize col0 = 1.
Traverse the matrix from top to bottom:
    If matrix[i][0] == 0, set col0 = 0.
    For every j = 1 to n-1:
        If matrix[i][j] == 0:
          Set matrix[i][0] = 0
          Set matrix[0][j] = 0
Traverse the matrix from bottom to top:
    For every j = n-1 to 1:
        If matrix[i][0] == 0 OR matrix[0][j] == 0
          Set matrix[i][j] = 0
    If col0 == 0
        Set matrix[i][0] = 0
@endsection
