Given an mXn matrix, if an element is 0, set its entire row and column to 0. Do it in-place
belongs to collection: interview C++ coding problems/challenges | Implementation
All Answers
total answers (1)
Severity: 8192
Message: str_replace(): Passing null to parameter #3 ($subject) of type array|string is deprecated
Filename: libraries/Filtered_db.php
Line Number: 23
belongs to collection: interview C++ coding problems/challenges | Implementation
total answers (1)
This problem asks you to solve in-place. It means you can only use constant extra space that is in O(1) space complexity.
We will use to boolean variable row and col variable which will be initially false. We will check each row and find if the first element of the given row is 0 or not. If 0 then we will assign row=true and break. Similarly, we will assign col variable with false initially and then we will make it true after checking it all column first elements.
Now, we will travel all elements for the matrix except first row and first column and check if the current element is 0 or not. If 0 then we will make the first element of that column and row as 0.
We will again iterate through all elements of the matrix except first column and first row and check if the current element's first element in that column or the first element in that row is zero or not, if zero then we will make the current element as 0.
Finally, if the row variable that we initially declare is true then we will make the first element of each row as 0, and if col variable is also true then we will make the first element of each col as 0.
Time Complexity for above approach in worst case is (n*m)
Space complexity for above approach in worst case is O(1)
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer