Katkat
Back

Advance Game of Life with Reduced Auxiliary Storage

Additive AiSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests array manipulation techniques, specifically bitwise operations and modular arithmetic, to transform a grid in-place while preserving original state information for simultaneous updates.

Problem Statement

The Game of Life is played on an m x n grid where each cell is either alive (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, and diagonal) according to these rules:

  1. A live cell with 3 live neighbors dies.
  2. A dead cell with exactly 3 live neighbors becomes alive.

Implement a function gameOfLife(board: List[List[int]]) -> None that updates the grid to the next generation in-place. You must not create a copy of the board.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 500

Example

Input:

[[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]]

Implementation Requirement

Since the update must be simultaneous, you cannot overwrite the current state without losing information required to calculate the next state for neighboring cells. Use the bitwise encoding strategy:

  • Use the second bit (value 2) to store the next state of a cell while the first bit (value 1) stores the current state.
  • After calculating all next states, perform a second pass to shift the bits.

Hints

Hint 1

To solve this in-place, you need a way to track the transition from the current state (0 or 1) to the future state without losing the original value.

Hint 2

Consider using the state of a cell as a 2-bit integer: the first bit represents the current status, and the second bit represents the status for the next generation.

Hint 3

After computing the next state, you can use the modulo operator or bitwise right-shift to extract the future state and update the board.

Follow-up questions

  • How would you modify this algorithm if the grid were so large (e.g., billions of cells) that it could not fit into memory, and you only have access to it via an external API?
  • Can you explain the time and space complexity of your solution, and how the bitwise approach affects the memory footprint?
  • If the grid had infinite boundaries, how would you represent the data structure to track only the active regions?