73 — Set Matrix Zeroes

Problem Description

Restating Info We’re Already Given:

• For each row and for each column, if there is a 0 in that respective row or column, we want to make all values in that row or column 0.
• We must do this in-place, so we cannot just recreate the array with zeroes filled in.

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• I can solve this with zero additional memory, but it will take 1 extra loop through the 2D array (still O(m*n) time complexity, but no additional space) or I can solve this with 1 less loop through the 2D array, but use constant memory. Which do you prefer?
• Given that I will fix it back to the appropriate final value, can I change indices values to be non-integer? i.e. char or string.

Discuss Naive Solution:

Naively, we could make a list/set of indice pairs containing pairs that should be converted to 0. Each time we encounter a zero in the array, we could append each index pair in that row and in that column to the list/set of indice pairs. After iterating through the 2D array, we can convert all indice pairs in the set to 0. The drawback to this solution is it takes up space linear to the number of 0’s in the 2D array, for a worst case O(m * n) space complexity. Also, the worst case time complexity is O((m + n) * m * n) because for each index equalling 0, we add the indice pairs for that row and column to the list (m + n pairs), so if each index contained a 0 then we reach our worst case runtime.

Discuss Alternative Solution:

If we can’t use any additional space, we could take advantage of the fact that each index contains an integer. We can have new values, the string “zero” to indicate an index that should at the end be converted to 0 and the string “fix” to indicate that each indice pair in that row and in that column should be converted to 0 at the end. In our first iteration, we convert all indice pairs equalling 0 to “fix” to signify that all values in that row and column should be converted to 0. Then in our next iteration, for all indices containing “fix”, we convert all integers in that row and column (including the index itself) to the string “zero” to later fix. Finally, we change all indices containing “zero” to the integer 0.

O(m*n) runtime, no additional space utilized

Discuss Optimal Solution:

We can use some variables to make the solution run 1 less loop through the 2D array at the cost of constant space. We use the row and column to indicate whether that respective row or column should be converted to zeroes. As we are possibly changing the value of the first row/column, we need 2 variables to store whether the first row or column should be converted to 0’s, firstColZero and firstRowZero. After determining whether the first row and/or the first column should be converted to 0’s, we then look at the rest of the array to convert the 0th row/column to 0. Then, for each index in the zeroth row/zeroth column, we make the rest of that respective row/column 0’s before potentially making the first column or first row zero, depending on the values of firstColZero and firstRowZero. We’re trading off 1 iteration through the entire 2D matrix for 2 booleans and 2 integer variables, or 24*2 + 24*2 = 96 bytes.

Code Optimal Solution:

O(m * n) time complexity, O(1) space complexity

Runtime/Space Complexity:

This runs in O(m * n) time because we run through the 2D array twice and through the first row and first column twice. The space complexity is O(1) since we have 2 boolean variables and 2 integer variables.

Test Cases:

• 1 x 1 matrix
• 1 x n matrix
• m x 1 matrix
• m x n matrix