0999MediumArrayMatrixSimulation

One Tick of a Lamp Grid

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A display panel holds lamps, each either lit as 1 or dark as 0. A lamp's neighbours are the cells touching it along an edge or at a corner, so up to eight of them.

On one tick every lamp changes at the same instant, and each one looks only at how many of its neighbours were lit just before the tick:

a lit lamp with fewer than two lit neighbours goes dark;
a lit lamp with two or three lit neighbours stays lit;
a lit lamp with more than three lit neighbours goes dark;
a dark lamp with exactly three lit neighbours comes on.

Return the panel as it stands after one tick.

Examples

Example 1

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

The middle lamp of the lit row keeps two lit neighbours and holds. The two ends have only one each and go dark. The cells straight above and below the middle each touch all three lit lamps, so they come on, leaving the row standing upright.

Example 2

Input: panel = [[1, 1], [1, 1]]
Output: [[1, 1], [1, 1]]

Each lamp touches the other three, so every one of them has three lit neighbours and stays lit. Nothing changes.

Example 3

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

The dark top-left cell touches three lit lamps and comes on. The lit lamp in the bottom-right corner touches only one and goes out. Two more dark cells, the one right of centre and the one below centre, each touch exactly three lit lamps and come on.

Constraints

1 <= panel.length <= 25
1 <= panel[i].length <= 25
0 <= panel[i][j] <= 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def game_of_life(panel: list[list[int]]) -> list[list[int]]:

Java

public int[][] gameOfLife(int[][] panel)

The intended approach

Time O(m * n) over the panel's cells.Space O(1) beyond the panel itself.

Everything changes at one instant, so each lamp's new state has to come from the states as they were before the tick. Writing a new state straight into a cell would spoil what that cell's neighbours still have to read. The way round that without a second panel is to hold both states in the same cell. Leave the old state in the lowest bit and write the new state into the bit above it. Counting a neighbour's old state then means reading its lowest bit, which nothing during the tick ever touches, so the order the cells are visited in stops mattering. Once every cell has been visited, sweep the panel again shifting each cell down by one, which drops the old states and leaves the panel after the tick. Two sweeps, up to eight neighbours read per cell, and no second panel.

Pythonentry point: game_of_life

def game_of_life(panel):
    rows = len(panel)
    cols = len(panel[0])
    for r in range(rows):
        for c in range(cols):
            lit = 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        lit += panel[nr][nc] & 1
            if panel[r][c] & 1:
                if lit == 2 or lit == 3:
                    panel[r][c] |= 2
            elif lit == 3:
                panel[r][c] |= 2
    for r in range(rows):
        for c in range(cols):
            panel[r][c] >>= 1
    return panel

The obvious version

Take a full copy of the panel first, then work out each lamp's new state by counting lit neighbours in the copy and writing the result straight into the panel. Spends a whole second panel's worth of room rather than packing the old and new states into the same cell.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_game_of_life(panel):
    rows = len(panel)
    cols = len(panel[0])
    before = [row[:] for row in panel]
    for r in range(rows):
        for c in range(cols):
            lit = 0
            for nr in range(r - 1, r + 2):
                for nc in range(c - 1, c + 2):
                    if nr == r and nc == c:
                        continue
                    if 0 <= nr < rows and 0 <= nc < cols:
                        lit += before[nr][nc]
            if before[r][c]:
                panel[r][c] = 1 if lit == 2 or lit == 3 else 0
            else:
                panel[r][c] = 1 if lit == 3 else 0
    return panel

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in