This question is in Cracking the coding interview. I forgot the solution there, I

This question is in Cracking the coding interview. I forgot the solution there, I did this question in O(n*m) time and O(n+k) time where k is less than or equal to m and memory complexity didn’t complain. my solution is:

  1. Initialise a row with all 0 values, since we know that the matrix has constant n which will be all the same, we can do that
  2. Initialise an empty hashset of integers
  3. Iterate through the list, for every row check if there is zero, if there is then add this character to the hashset, at the end of every row iteration, if there was 0, then change the reference of this row with the one on the step 1 (such as A.set(i, zeroRow) in Java)
  4. iterate through your set that you initialised on step 2, and within this iteration, iterate through all rows and use the integer to set the columns to 0.

To be more precise, the complete solution has the runtime complexity of O(2n+2m+(2nm)) wheras this one only has O(n + (nm) + (nk)) so it has a lot less constant complexity.

Hi Sarp,
If I understand correctly, the additional space complexity of the solution you proposed is not O(1), correct ?
According to the problem statement : "Note that this will be evaluated on the extra memory used. ".

Anshuman Singh Yes it;s not O(1), however this answer doesn’t fail, I’m guessing the main reason is because k is quite small, so it only uses n amount plus few bytes.

Click here to start solving coding interview questions