[LeetCode] Set Matrix Zeroes

문제

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: [   [1,1,1],   [1,0,1],   [1,1,1] ] Output: [   [1,0,1],   [0,0,0],   [1,0,1] ]

Example 2:

Input: [   [0,1,2,0],   [3,4,5,2],   [1,3,1,5] ] Output: [   [0,0,0,0],   [0,4,5,0],   [0,3,1,0] ]

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

Approach

가장 쉬운 방법은 0의 위치를 다 기록해두고 나중에 한번에 업데이트 하는거지만

이러면 공간복잡도가 O(mn)이라 bad idea라고 한다.

solution을 보니까 matrix[i][j]칸에 0이 나오면 그 행과 그 열은 모두 0이 될 것이므로

matrix[0][j]와 matrix[i][0], 즉 각 칸의 맨 앞 행과 맨 앞 열에 0이라고 기록해둔다.

matrix[0][0]은 이 방법으로는 0인지 아닌지 기록해둘 수 없으므로 따로 처리한다.

또한 각 행의 맨 앞 행이나 열은 위 방법으로 기록하면 원래 있던 값이 덮어써져서

원래 0이 있었는지 없었는지 알 수 없어지기 때문에 맨 앞 행이나 맨 앞 열은 따로 변수를 만들어

원래 0이 있었는지 없었는지 기록한다. (이 방법에서는 맨 앞 열을 따로 처리했다)

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_SetMatrixZeroes.cpp

chi3236/algorithm