Skip to content

353. Design Snake Game

On LeetCode ->

Problem

Implement SnakeGame(width, height, food) and move(direction). The snake starts at (0, 0). Each move advances its head, removes its tail unless it eats the next food, and returns the score. Hitting a wall or the snake's body ends the game; that move and all later moves return -1.

SnakeGame(3, 2, [[1, 2], [0, 1]])
moves:   R  D  R  U  L  U
returns: 0  0  1  1  2 -1

class SnakeGame:
    def __init__(self, width: int, height: int, food: list[list[int]]):
        pass

    def move(self, direction: str) -> int:
        pass

Key trick

Keep the body in a deque and its cells in a set. On a move without food, the head may enter the current tail's cell, because the tail leaves on that same move.

Trap

Checking occupancy before accounting for the departing tail rejects a legal move. Rejecting a reversal solely because it reverses direction is also wrong: the rules specify collisions, not a direction restriction.

Why is it interesting?

The collision result depends on whether the snake grows, so the order of state updates matters.

Python solution

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.score = 0
        self.over = False
        self.snake = deque([(0, 0)])  # Tail to head.
        self.occupied = {(0, 0)}

    def move(self, direction: str) -> int:
        if self.over:
            return -1

        dr, dc = {
            "U": (-1, 0),
            "D": (1, 0),
            "L": (0, -1),
            "R": (0, 1),
        }[direction]
        r, c = self.snake[-1]
        head = (r + dr, c + dc)

        if not (0 <= head[0] < self.height and 0 <= head[1] < self.width):
            self.over = True
            return -1

        eats = (
            self.score < len(self.food)
            and head == tuple(self.food[self.score])
        )

        # Without food, the current tail vacates its cell on this move.
        if head in self.occupied and (eats or head != self.snake[0]):
            self.over = True
            return -1

        if eats:
            self.score += 1
        else:
            tail = self.snake.popleft()
            self.occupied.remove(tail)

        self.snake.append(head)
        self.occupied.add(head)
        return self.score

Complexity: \(O(1)\) average time per move; \(O(L + F)\) space for snake length \(L\) and \(F\) food positions.

Comment on my solution

Your deque-and-set approach is the right one, and removing the tail before checking occupancy handles moves into its cell. The implementation needs these corrections:

  • Rename __init_ to __init__ and add self to move.
  • Use row/column offsets correctly: U changes the row by -1, and R changes the column by 1. Compare rows with height and columns with width.
  • Use self.score rather than score.
  • Remove the reversal check; a reversal is legal when it does not cause a collision.
  • Record game-over state so every later call returns -1.
# Ideas:
# - Use a queue for the current snake
#   - moving 1 position, we popleft the queue
# - combine it with a hashset, for O(1) check if the head
#   meet the body (after moving)
# - one move is forbidden, which is moving down (for instance)
#   while the snake prev move was moving up, you can't move back
#   - see if we have to implement this later

from collections import deque

# WRONG
class SnakeGame:
    def __init_(self, width: int, height: int, food: list[list[int]]):
        self.score = 0
        self.width = width
        self.height = height
        self.next_food_idx = 0
        self.food = food
        self.snake_queue = deque([(0,0)])
        self.snake_set = {(0,0)}
        self.prev_dir = None

    def move(direction: str):
        moves = {"U": (0,1), "D": (0,-1), "L": (-1,0), "R": (1,0)}

        if self.prev_dir and (self.prev_dir, direction) in (("U", "D"), ("D", "U"), ("L", "R"), ("R", "L")):
            return -1
        self.prev_dir = direction

        dr, dc = moves[direction]
        head_r, head_c = self.snake_queue[-1]
        nxt_head_r, nxt_head_c = head_r + dr, head_c + dc

        # out-of-bound
        if not (0 <= nxt_head_r < self.width) or not (0 <= nxt_head_c < self.height):
            return -1

        self.snake_queue.append((nxt_head_r, nxt_head_c))

        # Try to eat food
        ate = False
        if self.next_food_idx < len(self.food):
            food_cell = tuple(self.food[self.next_food_idx])
            if (nxt_head_r, nxt_head_c) == food_cell:
                score += 1
                self.next_food_idx += 1
                ate = True

        # remove the tail (corresponds to snake moving if it doesn't grow by 1)
        if not ate:
            tail = self.snake_queue.popleft()
            self.snake_set.remove(tail)

        # Does head meet its body?
        if (nxt_head_r, nxt_head_c) in self.snake_set:
            return -1

        self.snake_set.add((nxt_head_r, nxt_head_c))

        return score

Extra

Problem description

Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

  • SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
  • int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

Example 1:

  Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
  Output
[null, 0, 0, 1, 1, 2, -1]

  Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

Constraints:

  • 1 <= width, height <= 10^4
  • 1 <= food.length <= 50
  • food[i].length == 2
  • 0 <= ri < height
  • 0 <= ci < width
  • direction.length == 1
  • direction is 'U', 'D', 'L', or 'R'.
  • At most 10^4 calls will be made to move.

Coordinate U, D, L, and R

Are you sure for the value of U, D, L, R? I think they are for Up, Down, Left and Right? So my coordinate choices. And this seems to be what they use in the example. Am I missing something?

You're right that U, D, L, and R mean up, down, left, and right. The distinction is which coordinate comes first.

The problem gives positions as (row, column), not (x, y):

  • Up: row decreases → (-1, 0)
  • Down: row increases → (1, 0)
  • Left: column decreases → (0, -1)
  • Right: column increases → (0, 1)

In the example, the first R moves from (0, 0) to (0, 1). With your offset for R, it would move to (1, 0) instead. Your offsets would make sense for an (x, y) representation with a suitable choice of vertical direction, but then you'd need to convert the food positions from (row, column) and check x against width and y against height.