289. Game of Life / 73. Set Matrix Zeroes

289. Game of Life

시간 복잡도는 MN일수 밖에없고 공간복잡도는 단순하게 하면 MN이나 생각해보면 O(1)에도 구현할 수 있다. 어프로치2

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

콘웨이의 게임이라고도 알려져 있는 문제.

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

보드는 m x n셀 그리드 로 구성 되며, 각 셀의 초기 상태는 라이브 (로 표시 1) 또는 데드 (로 표시 0)입니다. 각 셀 은 위의 Wikipedia 기사에서 가져온 다음 네 가지 규칙을 사용하여 8 개의 이웃 (가로, 세로, 대각선) 과 상호 작용합니다 .

Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

살아있는 이웃이 두 개 미만인 모든 살아있는 세포는 인구 부족으로 인한 것처럼 죽습니다.
2 ~ 3 명의 살아있는 이웃이있는 살아있는 세포는 다음 세대를 위해 살아갑니다.
세 개 이상의 살아있는 이웃이있는 모든 살아있는 세포는 인구 과잉으로 죽는 것처럼 죽습니다.
정확히 세 개의 살아있는 이웃이있는 죽은 세포는 마치 번식에 의한 것처럼 살아있는 세포가됩니다.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

다음 상태는 출생과 죽음이 동시에 일어나는 현재 상태의 모든 세포에 위의 규칙을 동시에 적용하여 생성됩니다. m x n그리드 의 현재 상태가 주어지면 다음 상태를board 반환 합니다 .

Example 1:

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

Example 2:

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

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] is 0 or 1.

Follow up:

Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

제자리에서 해결할 수 있습니까? 보드를 동시에 업데이트해야합니다. 먼저 일부 셀을 업데이트 한 다음 업데이트 된 값을 사용하여 다른 셀을 업데이트 할 수 없습니다.
이 질문에서 우리는 2D 배열을 사용하여 보드를 나타냅니다. 원칙적으로 보드는 무한하므로 활성 영역이 어레이의 경계를 침범 할 때 문제가 발생할 수 있습니다 (즉, 라이브 셀이 경계에 도달). 이러한 문제를 어떻게 해결 하시겠습니까?

Solution

Before moving on to the actual solution, let us visually look at the rules to be applied to the cells to get a greater clarity.

Approach 1: O(mn) Space Solution

Intuition

The problem might look very easy at first, however, the most important catch in this problem is to realize that if you update the original array with the given rules, you won't be able to perform simultaneous updation as is required in the question. You might end up using the updated values for some cells to update the values of other cells. But the problem demands applying the given rules simultaneously to every cell.

Thus, you cannot update some cells first and then use their updated values to update other cells.

In the above diagram it's evident that an update to a cell can impact the other neighboring cells. If we use the updated value of a cell while updating its neighbors, then we are not applying rules to all cells simultaneously.

Here simultaneously isn't about parallelism but using the original values of the neighbors instead of the updated values while applying rules to any cell. Hence the first approach could be as easy as having a copy of the board. The copy is never mutated. So, you never lose the original value for a cell.

Whenever a rule is applied to any of the cells, we look at its neighbors in the unmodified copy of the board and change the original board accordingly. Here we keep the copy unmodified since the problem asks us to make the changes to the original array in-place.

Algorithm

Make a copy of the original board which will remain unchanged throughout the process.
Iterate the cells of the Board one by one.
While computing the results of the rules, use the copy board and apply the result in the original board.

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1),(0,1),(1,1)]
        rows = len(board)
        cols = len(board[0])
        
        copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]
        
        for row in range(rows):
            for col in range(cols):
                live_neighbors = 0
                for neighbor in neighbors:
                    r = (row + neighbor[0])
                    c = (col + neighbor[1])
                    
                    if ( r < rows and r >= 0) and (c < cols and c >= 0) and (copy_board[r][c] == 1):
                        live_neighbors += 1
                if copy_board[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[row][col] = 0
                if copy_board[row][col] == 0 and live_neighbors == 3:
                    board[row][col] = 1

Complexity Analysis

Time Complexity: O(M \times N), where M is the number of rows and N is the number of columns of the Board.
Space Complexity: O(M \times N), where M is the number of rows and N is the number of columns of the Board. This is the space occupied by the copy board we created initially.

Approach 2: O(1) Space Solution

Intuition

The problem could also be solved in-place. O(M \times N) space complexity could be too expensive when the board is very large. We only have two states live(1) or dead(0) for a cell. We can use some dummy cell value to signify previous state of the cell along with the new changed value.

For e.g. If the value of the cell was 1 originally but it has now become 0 after applying the rule, then we can change the value to -1. The negative sign signifies the cell is now dead(0) but the magnitude signifies the cell was a live(1) cell originally.

Also, if the value of the cell was 0 originally but it has now become 1 after applying the rule, then we can change the value to 2. The positive sign signifies the cell is now live(1) but the magnitude of 2 signifies the cell was a dead(0) cell originally.

문제는 제자리에서 해결 될 수도 있습니다. O (M \ times N)보드가 매우 큰 경우 공간 복잡성이 너무 비쌀 수 있습니다. 우리는 단지 두 개의 상태 live(1)또는 dead(0)세포를 가지고 있습니다. 더미 셀 값을 사용하여 새로 변경된 값과 함께 셀의 이전 상태를 나타낼 수 있습니다.

예를 들어 셀의 값이 1원래 였지만 0규칙을 적용한 후 이제 값이 된 경우 값을로 변경할 수 있습니다 -1. 음수 sign는 셀이 이제 죽었 음을 의미하지만 (0) magnitude원래 셀이 라이브 (1) 셀 이었음을 의미합니다.

또한 셀의 값이 0원래 였지만 이제 1규칙을 적용한 후에 값이 되었으면 값을로 변경할 수 있습니다 2. 양수 sign는 셀이 현재 라이브 (1) magnitude임을 의미 하지만, 2는 셀이 원래 죽은 (0) 셀임을 의미합니다.

Algorithm

Iterate the cells of the Board one by one.
The rules are computed and applied on the original board. The updated values signify both previous and updated value.
The updated rules can be seen as this:
- Rule 1: Any live cell with fewer than two live neighbors dies, as if caused by under-population. Hence, change the value of cell to -1. This means the cell was live before but now dead.
- Rule 2: Any live cell with two or three live neighbors lives on to the next generation. Hence, no change in the value.
- Rule 3: Any live cell with more than three live neighbors dies, as if by over-population. Hence, change the value of cell to -1. This means the cell was live before but now dead. Note that we don't need to differentiate between the rule 1 and 3. The start and end values are the same. Hence, we use the same dummy value.
- Rule 4: Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Hence, change the value of cell to 2. This means the cell was dead before but now live.
Apply the new rules to the board.
Since the new values give an indication of the old values of the cell, we accomplish the same results as approach 1 but without saving a copy.
To get the Board in terms of binary values i.e. live(1) and dead(0), we iterate the board again and change the value of a cell to a 1 if its value currently is greater than 0 and change the value to a 0 if its current value is lesser than or equal to 0.

규칙 1 : 살아있는 이웃이 2 개 미만인 모든 살아있는 세포는 인구 부족으로 인한 것처럼 죽습니다. 따라서 cell의 값을 -1. 이것은 세포가 이전에 살았지만 지금은 죽었 음을 의미합니다.
규칙 2 : 2 ~ 3 명의 살아있는 이웃이있는 살아있는 세포는 다음 세대를 위해 살아갑니다. 따라서 값에 변화가 없습니다.
규칙 3 : 세 개 이상의 살아있는 이웃이있는 살아있는 세포는 마치 과밀로 죽는 것처럼 죽습니다. 따라서 cell의 값을 -1. 이것은 세포가 이전에 살았지만 지금은 죽었 음을 의미합니다. 규칙 1과 3을 구분할 필요가 없습니다. 시작 값과 끝 값이 동일합니다. 따라서 동일한 더미 값을 사용합니다.
규칙 4 : 정확히 세 개의 살아있는 이웃이있는 죽은 세포는 마치 번식에 의한 것처럼 살아있는 세포가됩니다. 따라서 cell의 값을 2로 변경합니다. 이것은 이전에 세포가 죽었지 만 지금은 살아 있음을 의미합니다.

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # Neighbors array to find 8 neighboring cells for a given cell
        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

        rows = len(board)
        cols = len(board[0])

        # Iterate through board cell by cell.
        for row in range(rows):
            for col in range(cols):

                # For each cell count the number of live neighbors.
                live_neighbors = 0
                for neighbor in neighbors:

                    # row and column of the neighboring cell
                    r = (row + neighbor[0])
                    c = (col + neighbor[1])

                    # Check the validity of the neighboring cell and if it was originally a live cell.
                    if (r < rows and r >= 0) and (c < cols and c >= 0) and abs(board[r][c]) == 1:
                        live_neighbors += 1

                # Rule 1 or Rule 3
                if board[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    # -1 signifies the cell is now dead but originally was live.
                    board[row][col] = -1
                # Rule 4
                if board[row][col] == 0 and live_neighbors == 3:
                    # 2 signifies the cell is now live but was originally dead.
                    board[row][col] = 2

        # Get the final representation for the newly updated board.
        for row in range(rows):
            for col in range(cols):
                if board[row][col] > 0:
                    board[row][col] = 1
                else:
                    board[row][col] = 0

Complexity Analysis

Time Complexity: O(M \times N), where M is the number of rows and N is the number of columns of the Board.
Space Complexity: O(1)

Follow up 2 : Infinite Board

So far we've only addressed one of the follow-up questions for this problem statement. We saw how to perform the simulation according to the four rules in-place i.e. without using any additional memory. The problem statement also mentions another follow-up statement which is a bit open ended. We will look at two possible solutions to address it. Essentially, the second follow-up asks us to address the scalability aspect of the problem. What would happen if the board is infinitely large? Can we still use the same solution that we saw earlier or is there something else we will have to do different? If the board becomes infinitely large, there are multiple problems our current solution would run into:

It would be computationally impossible to iterate a matrix that large.
It would not be possible to store that big a matrix entirely in memory. We have huge memory capacities these days i.e. of the order of hundreds of GBs. However, it still wouldn't be enough to store such a large matrix in memory.
We would be wasting a lot of space if such a huge board only has a few live cells and the rest of them are all dead. In such a case, we have an extremely sparse matrix and it wouldn't make sense to save the board as a "matrix".

Such open ended problems are better suited to design discussions during programming interviews and it's a good habit to take into consideration the scalability aspect of the problem since your interviewer might be interested in talking about such problems. The discussion section already does a great job at addressing this specific portion of the problem. We will briefly go over two different solutions that have been provided in the discussion sections, as they broadly cover two main scenarios of this problem.

One aspect of the problem is addressed by a great solution provided by Stefan Pochmann. So as mentioned before, it's quite possible that we have a gigantic matrix with a very few live cells. In that case it would be stupidity to save the entire board as is.

If we have an extremely sparse matrix, it would make much more sense to actually save the location of only the live cells and then apply the 4 rules accordingly using only these live cells.

Let's look at the sample code provided by Stefan for handling this aspect of the problem.

Essentially, we obtain only the live cells from the entire board and then apply the different rules using only the live cells and finally we update the board in-place. The only problem with this solution would be when the entire board cannot fit into memory. If that is indeed the case, then we would have to approach this problem in a different way. For that scenario, we assume that the contents of the matrix are stored in a file, one row at a time.

In order for us to update a particular cell, we only have to look at its 8 neighbors which essentially lie in the row above and below it. So, for updating the cells of a row, we just need the row above and the row below. Thus, we read one row at a time from the file and at max we will have 3 rows in memory. We will keep discarding rows that are processed and then we will keep reading new rows from the file, one at a time.

@beagle's solution revolves around this idea and you can refer to the code in the discussion section for the same. It's important to note that there is no single solution for solving this problem. Everybody might have a different viewpoint for addressing the scalability aspect of the problem and these two solutions just address the most basic problems with handling matrix based problems at scale.

class Solution:
    def gameOfLifeInfinite(self, live):
        ctr = collections.Counter((I, J)
                                  for i, j in live
                                  for I in range(i-1, i+2)
                                  for J in range(j-1, j+2)
                                  if I != i or J != j)
        return {ij
                for ij in ctr
                if ctr[ij] == 3 or ctr[ij] == 2 and ij in live}

    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        live = {(i, j) for i, row in enumerate(board) for j, live in enumerate(row) if live}
        live = self.gameOfLifeInfinite(live)
        for i, row in enumerate(board):
            for j in range(len(row)):
                row[j] = int((i, j) in live)

73. Set Matrix Zeroes

leetcode.com/problems/set-matrix-zeroes/

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

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?

Example 1:

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

Example 2:

Input: matrix = [[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]]

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don't want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.

Hide Hint 2

Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with 0(1) space.

Hide Hint 3

We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.

Hide Hint 4

We can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero.

Solution

The question seems to be pretty simple but the trick here is that we need to modify the given matrix in place i.e. our space complexity needs to O(1).

We will go through two different approaches to the question. The first approach makes use of additional memory while the other does not.

Approach 1: Additional Memory Approach

Intuition

If any cell of the matrix has a zero we can record its row and column number. All the cells of this recorded row and column can be marked zero in the next iteration.

Algorithm

We make a pass over our original array and look for zero entries.
If we find that an entry at [i, j] is 0, then we need to record somewhere the row i and column j.
So, we use two sets, one for the rows and one for the columns.
if cell[i][j] == 0 { row_set.add(i) column_set.add(j) }
Finally, we iterate over the original matrix. For every cell we check if the row r or column c had been marked earlier. If any of them was marked, we set the value in the cell to 0.
if r in row_set or c in column_set { cell[r][c] = 0 }

Complexity Analysis

Time Complexity: O(M \times N) where M and N are the number of rows and columns respectively.
Space Complexity: O(M + N).

Approach 2: O(1) Space, Efficient Solution

Intuition

Rather than using additional variables to keep track of rows and columns to be reset, we use the matrix itself as the indicators.

The idea is that we can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero. This means for every cell instead of going to M+N cells and setting it to zero we just set the flag in two cells.

if cell[i][j] == 0 { cell[i][0] = 0 cell[0][j] = 0 }

These flags are used later to update the matrix. If the first cell of a row is set to zero this means the row should be marked zero. If the first cell of a column is set to zero this means the column should be marked zero.

Algorithm

We iterate over the matrix and we mark the first cell of a row i and first cell of a column j, if the condition in the pseudo code above is satisfied. i.e. if cell[i][j] == 0.
The first cell of row and column for the first row and first column is the same i.e. cell[0][0]. Hence, we use an additional variable to tell us if the first column had been marked or not and the cell[0][0] would be used to tell the same for the first row.
Now, we iterate over the original matrix starting from second row and second column i.e. matrix[1][1] onwards. For every cell we check if the row r or column c had been marked earlier by checking the respective first row cell or first column cell. If any of them was marked, we set the value in the cell to 0. Note the first row and first column serve as the row_set and column_set that we used in the first approach.
We then check if cell[0][0] == 0, if this is the case, we mark the first row as zero.
And finally, we check if the first column was marked, we make all entries in it as zeros.