Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Created LeetCode73 Set Matrix Zeros (Medium) #369 #458

Closed
wants to merge 1 commit into from
Closed

Created LeetCode73 Set Matrix Zeros (Medium) #369 #458

wants to merge 1 commit into from

Conversation

thatdamncoder
Copy link

Created
Fixed #369

Question Link:- https://leetcode.com/problems/set-matrix-zeroes/

Language-Java

Question-
Given an m x n integer matrix 'matrix', if an element is 0, set its entire row and column to 0's.
You must do it in place.

Intuition-

  1. This problem can be solved by many approaches
  2. You can have
    2.1 Brute Force
    Traverse through the entire array, element by element, if the element is zero, traverse the column and row for it to make them '-1' ( or any other non-zero number - making them zero in the first place would lead to unexpected results). This would take a Time O(n3).
    2.2 Brute Force 2
    You could create two 1-D arrays for storing the occurrence of zeros in each row and each column. In the end, setting all those rows/cols to zero if the respective 1-D array indicated so. But this would take an extra space for both the 1-D arrays.

Approach:-
Identify and Mark Zeros: Traverse the matrix and mark the first cell of corresponding rows and columns as zero if any element is zero. Use two boolean variables, firstRow and firstCol, to keep track of whether the first row or first column contains any zeros.

Make Rows and Columns Zeros: Iterate through the matrix again, excluding the first row and the first column, and set the elements to zero if the corresponding row or column's first element is zero.

Update First Row and First Column: Finally, based on the boolean flags firstRow and firstCol, if any of them are true, update the entire first row or first column to zero accordingly.

Complexities:-
Time - O(n2),since the minimum time to traverse a 2-D array is O(n2)
Space- O(1), since no extra space

How to Proceed:-

  1. Understand the solution
  2. Try yourself
  3. Edit your array accordingly to check my solution
  4. If satisfied, submit on LeetCode

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Leetcode problem 73 . Set Matrix Zeroes
2 participants