Practice/Amazon/Leetcode 289. Game of Life

Leetcode 289. Game of Life

CodingMust

Problem

You are building a cellular automaton simulator. Given a 2D grid where each cell is either alive (represented by 1) or dead (represented by 0), compute the next generation of the grid according to these evolution rules:

1. Any living cell with fewer than 2 living neighbors dies (underpopulation)
2. Any living cell with 2 or 3 living neighbors survives to the next generation
3. Any living cell with more than 3 living neighbors dies (overpopulation)
4. Any dead cell with exactly 3 living neighbors becomes alive (reproduction)

Each cell has up to 8 neighbors: the cells directly adjacent horizontally, vertically, and diagonally.

The key challenge is that all cells must be evaluated simultaneously based on the current generation's state. You cannot update cells one-by-one because that would affect the neighbor counts for subsequent cells.

You should modify the grid in-place and return it.

Requirements

1. Update all cells simultaneously based on the current state
2. Consider all 8 directions when counting neighbors (horizontal, vertical, and diagonal)
3. Handle edge and corner cells correctly (they have fewer than 8 neighbors)
4. Modify the grid in-place
5. Return the updated grid

Constraints

• m == grid.length (number of rows)
• n == grid[i].length (number of columns)
• 1 <= m, n <= 25
• grid[i][j] is either 0 or 1
• Aim for O(m × n) time complexity
• Try to achieve O(1) extra space (not counting the input grid)

Examples

Example 1:

` Input: grid = [ [0,1,0], [0,1,0], [0,1,0] ] Output: [ [0,0,0], [1,1,1], [0,0,0] ] Explanation:

• Top middle cell (1): has 1 neighbor → dies
• Center cell (1): has 2 neighbors → survives
• Bottom middle cell (1): has 1 neighbor → dies
• Middle left cell (0): has 3 neighbors → becomes alive
• Middle right cell (0): has 3 neighbors → becomes alive `

Example 2:

Input: grid = [ [0,0,0,0], [0,1,1,0], [0,1,1,0], [0,0,0,0] ] Output: [ [0,0,0,0], [0,1,1,0], [0,1,1,0], [0,0,0,0] ] Explanation: This is a stable "block" pattern. Each living cell has exactly 3 neighbors, so they all survive. The dead cells don't have exactly 3 neighbors, so they stay dead.

Example 3:

Input: grid = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: The single cell has no neighbors and dies from underpopulation.