Jul 17, 2024

- World's most in-depth DS algo course with 55 modules and over 400 problems.
- Completing the course guarantees the ability to clear DS algo rounds in any company globally.
- Today's topic: Problem Set Matrix Zeros.

- Given an NxM binary matrix (only 0s and 1s).
- Task: For every zero, mark its entire row and column with zeros.
- Important: Only consider initial zeros, changes made during process should not affect others.

- Iterate through NxM matrix.
- When a zero is found, mark entire row and column with zeros.
- Repeat until all initial zeros are processed.

- Marks previously changed 0s in subsequent iterations, causing incorrect results.
- Needs careful handling of marking to avoid above issues.

- Use
`-1`

instead of`0`

for marking changes during iterations. - Convert
`-1`

to`0`

in the final iteration.

- Traverse NxM matrix and mark zeros with
`-1`

where required. - Traverse matrix again to convert all
`-1`

to`0`

.

- Traversal: O(NxM)
- Marking columns and rows: O(N+M)
- Overall: O(NxM * (N+M)) ≈ O(N^3)

- Each zero in the matrix affects its entire row and column.
- Instead of updating the matrix during the traversal, use two auxiliary arrays to keep track of rows and columns to be zeroed out.

- Use two arrays of size N and M to keep track of affected rows and columns.
- Traverse the matrix to populate these arrays.
- Update the matrix in a second pass using these arrays.

- Traverse the matrix and populate row and column arrays.
- Traverse again and update the matrix.

- Time: O(NxM)
- Space: O(N+M) due to additional tracking arrays.

- Try to use the matrix itself for marking to avoid extra space usage.
- Use first row and column for marking zeros.

- Utilize the first row and column as auxiliary arrays.
- Handle special case where the first cell is part of both first row and column.

- Traverse matrix to mark zeros in the first row and column, except the first cell.
- Traverse matrix again to mark the matrix using first row and column's markers.
- Update the first row and column separately.
- Handle the first cell separately due to dual role.

- Initialize space for column flag.
- Mark rows and column using initial pass, handle column zero separately.
- Second pass to update matrix except the first row and column.
- Final pass to update the first row and column based on initial markers.

- Time: O(NxM)
- Space: O(1) (In-place modification)

- Three approaches discussed: Brute Force, Optimized with auxiliary space, Optimal In-Place solution.
- Trade-offs between time complexity and space usage.
- Optimal in-place solution is efficient for interviews.

- Problem description and code links in video description.
- Follow on Instagram, Twitter, LinkedIn.
- Like, share, and subscribe to the channel for more content.

**Understand and implement the optimal solution for efficient DS algo practices!**