LeetCode 353: Design Snake Game

Problem Restatement

We need to implement a simplified Snake game.

The screen has size:

height x width

The snake starts at the top-left cell:

(0, 0)

Its initial length is 1.

We are given a list of food positions. Food appears one at a time. The second food appears only after the snake eats the first food.

Each call to move(direction) moves the snake one cell in one of four directions:

"U" = up
"D" = down
"L" = left
"R" = right

After a move:

The method returns the current score after a valid move.

The problem statement specifies the constructor as SnakeGame(int width, int height, int[][] food) and the move method as int move(String direction). The snake starts at (0, 0), food positions are given as row-column pairs, and game over happens when the snake goes out of bounds or its head occupies a body cell after moving.

Input and Output

The food array looks like this:

food = [[1, 2], [0, 1]]

That means:

Only the current food is active.

Examples

Example input:

snakeGame = SnakeGame(3, 2, [[1, 2], [0, 1]])

The board has:

height = 2
width = 3

So valid rows are:

0, 1

Valid columns are:

0, 1, 2

The snake starts at:

(0, 0)

Now run the moves:

snakeGame.move("R")  # 0
snakeGame.move("D")  # 0
snakeGame.move("R")  # 1
snakeGame.move("U")  # 1
snakeGame.move("L")  # 2
snakeGame.move("U")  # -1

Step by step:

First Thought: Store the Whole Board

One direct design is to keep a full height x width grid.

Each cell could store whether it is empty, occupied by the snake, or contains food.

That works, but the board can be large, and we do not need to inspect every cell.

Each move only changes two places:

1. A new head cell is added.
2. The old tail cell is removed, unless food is eaten.

So we only need to track the snake body.

Key Insight

The snake body needs two operations:

The deque stores the snake body in order.

We will store the head at the left side and the tail at the right side:

head ... tail

For example:

deque([(0, 2), (0, 1), (0, 0)])

The occupied set stores the same cells for O(1) lookup:

{(0, 2), (0, 1), (0, 0)}

The subtle part is self-collision.

Before checking whether the new head collides with the body, we should remove the tail if the snake is not eating food.

Why?

Because moving into the current tail cell is allowed if the tail moves away during the same step.

Algorithm

Maintain:

For each move:

1. Read the current head.
2. Compute the next head using the direction.
3. Check wall collision.
4. Check whether the next head is the current food.
5. If the snake does not eat food, remove the tail from both body and occupied.
6. Check whether the next head is already occupied.
7. If occupied, return -1.
8. Add the new head to both body and occupied.
9. If food was eaten, advance food_index and increase score.
10. Return score.

Correctness

The deque always stores the snake body in head-to-tail order.

At initialization, the snake contains only (0, 0), so the deque and occupied set are correct.

For each valid move, the algorithm computes exactly one new head cell from the given direction. If that cell is outside the grid, the snake has hit a wall, so returning -1 is correct.

If the new head reaches the active food, the snake grows. The algorithm keeps the old tail, adds the new head, and increments the score. This increases the body length by one, matching the game rule.

If the new head does not reach food, the snake keeps the same length. The algorithm removes the old tail and then adds the new head. This models the body shifting forward by one cell.

The occupied set is updated together with the deque. Therefore, after removing the tail when needed, occupied represents exactly the cells that remain occupied before the new head is inserted.

The self-collision check then tests whether the new head occupies a remaining body cell. If it does, the game is over. If it does not, adding the new head produces the correct next snake state.

Therefore each move returns the correct score for valid moves and -1 for invalid moves.

Complexity

Let L be the current snake length.

Each move performs constant-time deque and set operations.

Implementation

from collections import deque

class SnakeGame:

    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0
        self.score = 0

        self.body = deque([(0, 0)])
        self.occupied = {(0, 0)}

        self.delta = {
            "U": (-1, 0),
            "D": (1, 0),
            "L": (0, -1),
            "R": (0, 1),
        }

    def move(self, direction: str) -> int:
        head_row, head_col = self.body[0]
        row_delta, col_delta = self.delta[direction]

        next_head = (
            head_row + row_delta,
            head_col + col_delta,
        )

        next_row, next_col = next_head

        if (
            next_row < 0
            or next_row >= self.height
            or next_col < 0
            or next_col >= self.width
        ):
            return -1

        eats_food = (
            self.food_index < len(self.food)
            and self.food[self.food_index] == [next_row, next_col]
        )

        if not eats_food:
            tail = self.body.pop()
            self.occupied.remove(tail)

        if next_head in self.occupied:
            return -1

        self.body.appendleft(next_head)
        self.occupied.add(next_head)

        if eats_food:
            self.food_index += 1
            self.score += 1

        return self.score

Code Explanation

The snake body is initialized with one cell:

self.body = deque([(0, 0)])
self.occupied = {(0, 0)}

The deque lets us add a head and remove a tail in constant time.

The set lets us check body collision in constant time.

Directions are stored as row and column changes:

self.delta = {
    "U": (-1, 0),
    "D": (1, 0),
    "L": (0, -1),
    "R": (0, 1),
}

For every move, we compute the new head:

head_row, head_col = self.body[0]
row_delta, col_delta = self.delta[direction]

next_head = (
    head_row + row_delta,
    head_col + col_delta,
)

Then we check whether it goes outside the board:

if (
    next_row < 0
    or next_row >= self.height
    or next_col < 0
    or next_col >= self.width
):
    return -1

Food is eaten only if the new head reaches the currently active food:

eats_food = (
    self.food_index < len(self.food)
    and self.food[self.food_index] == [next_row, next_col]
)

If no food is eaten, the snake length should stay the same. So the old tail leaves the board:

if not eats_food:
    tail = self.body.pop()
    self.occupied.remove(tail)

This happens before the self-collision check because moving into the old tail position is allowed when the tail moves away.

Then we check self-collision:

if next_head in self.occupied:
    return -1

If the move is valid, insert the new head:

self.body.appendleft(next_head)
self.occupied.add(next_head)

If food was eaten, update score and advance to the next food:

if eats_food:
    self.food_index += 1
    self.score += 1

Testing

def run_tests():
    game = SnakeGame(3, 2, [[1, 2], [0, 1]])

    assert game.move("R") == 0
    assert game.move("D") == 0
    assert game.move("R") == 1
    assert game.move("U") == 1
    assert game.move("L") == 2
    assert game.move("U") == -1

    game = SnakeGame(2, 2, [])
    assert game.move("R") == 0
    assert game.move("D") == 0
    assert game.move("L") == 0
    assert game.move("U") == 0

    game = SnakeGame(3, 3, [[0, 1], [0, 2], [1, 2], [1, 1]])
    assert game.move("R") == 1
    assert game.move("R") == 2
    assert game.move("D") == 3
    assert game.move("L") == 4
    assert game.move("U") == -1

    print("all tests passed")

run_tests()

Test meaning: