Design Snake Game

Medium Design Data Structures Queue / Circular Buffer Original on LeetCode

Reported atAtlassian

Design Snake Game is a medium design data structures problem solved with the queue / circular buffer pattern. The best approach, optimal (deque + hash set of occupied cells), runs in O(1) per move time and O(L + F) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list body, scan for collisions) up.

Problem

Design the classic Snake game on a board with height rows and width columns. The snake starts as a single cell at the top-left corner (0, 0). You are also given food, a list of cells [row, col]; the pieces appear one at a time in that order, and the next one shows up only after the current one has been eaten.

Implement SnakeGame:

  • SnakeGame(int width, int height, int[][] food) sets up the board and the food list.
  • int move(String direction) moves the head one cell "U" (up), "D" (down), "L" (left) or "R" (right) and returns the score, the number of food pieces eaten so far. When the head lands on the current food, the snake grows by one cell (its tail stays where it was) and the score goes up by one.

The game ends when the head leaves the board or runs into the snake’s own body. The tail moves out of its cell in the same step, so stepping into the cell the tail is just leaving is fine. When a move ends the game, return -1; every later call to move also returns -1.

Examples

Example 1

Input
SnakeGame(3, 2, [[1, 2], [0, 1]]), move("R"), move("D"), move("R"), move("U"), move("L"), move("U")
Output
0, 0, 1, 1, 2, -1
Why
The snake reaches the first food at (1,2) on the third move and the second at (0,1) on the fifth; the last move leaves the board through the top.

Example 2

Input
SnakeGame(2, 2, [[0, 1], [1, 1], [1, 0]]), move("R"), move("D"), move("L"), move("U"), move("R"), move("L"), move("D")
Output
1, 2, 3, 3, 3, -1, -1
Why
After three meals the snake fills the board. Moving into the cell the tail is just leaving is allowed, but turning back onto (0,0) hits the body; after that every move returns -1.

Constraints

  • 1 <= width, height <= 10^4
  • 1 <= food.length <= 50
  • food[i] = [row, col] with 0 <= row < height and 0 <= col < width
  • direction is one of "U", "D", "L", "R".
  • At most 10^4 calls to move.
  • A food item never appears on a cell occupied by the snake, and it is never at (0, 0).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (list body, scan for collisions)O(L) per moveO(L + F)
Optimal (deque + hash set of occupied cells)O(1) per moveO(L + F)

1Brute force (list body, scan for collisions)

TimeO(L) per moveThe collision check scans all L cells of the snake.
SpaceO(L + F)The body list holds L cells and the food list F items.

Keep the body as a list of cells with the head at the front. For each move compute the new head, check the walls, decide whether it eats the next food, remove the tail if it does not, then scan the whole body to see whether the new head lands on it.

  1. If the game is already over, return -1.
  2. Compute the new head from the direction; if it is off the board, end the game and return -1.
  3. eat is true when the next unused food sits on the new head. If not eating, remove the last cell of the body.
  4. Scan the body; if any cell equals the new head, end the game and return -1.
  5. Add the new head at the front. If eating, increase the score and move to the next food. Return the score.
class SnakeGame {
    private final int width, height;
    private final int[][] food;
    private final LinkedList<int[]> body = new LinkedList<>();
    private int foodIdx = 0, score = 0;
    private boolean over = false;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        body.addFirst(new int[] { 0, 0 });
    }

    public int move(String direction) {
        if (over) return -1;
        int r = body.getFirst()[0], c = body.getFirst()[1];
        switch (direction) {
            case "U": r--; break;
            case "D": r++; break;
            case "L": c--; break;
            default: c++;
        }
        if (r < 0 || r >= height || c < 0 || c >= width) {
            over = true;
            return -1;
        }
        boolean eat = foodIdx < food.length && food[foodIdx][0] == r && food[foodIdx][1] == c;
        if (!eat) body.removeLast();
        for (int[] cell : body) {
            if (cell[0] == r && cell[1] == c) {
                over = true;
                return -1;
            }
        }
        body.addFirst(new int[] { r, c });
        if (eat) {
            score++;
            foodIdx++;
        }
        return score;
    }
}

2Optimal (deque + hash set of occupied cells)

TimeO(1) per moveEach move does a constant number of deque and hash-set operations.
SpaceO(L + F)The deque and the set each hold the L cells of the snake; the food list holds F items.

Keep the same move logic, but store the body in a deque of encoded cells (row * width + col) and mirror it in a hash set. Removing the tail and adding the head touch both structures in O(1), and the collision test becomes a single set lookup.

  1. Start with the deque and the set both holding cell 0.
  2. On a move, compute the new head and check the walls.
  3. If it does not eat, pop the tail from the deque and remove it from the set.
  4. If the set already contains the new head, the snake bit itself: end the game.
  5. Push the head onto the deque and into the set; on eating, bump the score and the food index.
class SnakeGame {
    private final int width, height;
    private final int[][] food;
    private final Deque<Integer> body = new ArrayDeque<>();
    private final Set<Integer> occupied = new HashSet<>();
    private int foodIdx = 0, score = 0;
    private boolean over = false;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        body.addFirst(0);
        occupied.add(0);
    }

    public int move(String direction) {
        if (over) return -1;
        int head = body.peekFirst();
        int r = head / width, c = head % width;
        switch (direction) {
            case "U": r--; break;
            case "D": r++; break;
            case "L": c--; break;
            default: c++;
        }
        if (r < 0 || r >= height || c < 0 || c >= width) {
            over = true;
            return -1;
        }
        boolean eat = foodIdx < food.length && food[foodIdx][0] == r && food[foodIdx][1] == c;
        if (!eat) occupied.remove(body.pollLast());
        int cell = r * width + c;
        if (occupied.contains(cell)) {
            over = true;
            return -1;
        }
        body.addFirst(cell);
        occupied.add(cell);
        if (eat) {
            score++;
            foodIdx++;
        }
        return score;
    }
}

Edge cases to test

  • Moving into the cell the tail is leaving on the same move is allowed (unless the snake is eating, because then the tail stays)
  • Leaving the board on any side ends the game
  • After the game is over, every further call returns -1
  • All food eaten: the snake keeps moving without growing
  • A one-cell-wide board: the snake can only move along a single line

Hints

Hint 1

Store the snake as a sequence of cells from tail to head. A normal move adds a new head and drops the tail; eating adds a head and keeps the tail.

Hint 2

Order matters: drop the tail before checking whether the new head hits the body, otherwise following your own tail looks like a crash.

Hint 3

A deque gives O(1) head and tail updates; a hash set of occupied cells next to it gives O(1) collision checks.

FAQ

What is the best time complexity for Design Snake Game?

Optimal (deque + hash set of occupied cells) runs in O(1) per move time and O(L + F) extra space. Each move does a constant number of deque and hash-set operations.

Which pattern does Design Snake Game use?

It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Hit Counter, Design Circular Queue, First Unique Number.

Is there a brute force solution for Design Snake Game?

Yes. Brute force (list body, scan for collisions) takes O(L) per move time and O(L + F) space. Keep the body as a list of cells with the head at the front.

Which edge cases should I test for Design Snake Game?

Moving into the cell the tail is leaving on the same move is allowed (unless the snake is eating, because then the tail stays); Leaving the board on any side ends the game; After the game is over, every further call returns -1; All food eaten: the snake keeps moving without growing; A one-cell-wide board: the snake can only move along a single line.