Design Snake Game

Medium · Arrays & Hashing · Explanation and code example

Queue and Hash Set

How it works

The snake game requires tracking the snake's body as it moves and grows. A deque (double-ended queue) is perfect because we add to the front (new head position) and remove from the back (tail moves forward). To quickly check whether the snake bites itself, we also maintain a hash set of all occupied cells. When the snake eats food, the tail stays in place so the snake grows. The score equals the number of food items eaten, which is the snake length minus 1.

Steps

  1. Initialization: Create a deque with the snake starting at (0, 0). Add this position to a hash set. Store the grid dimensions, food list, and a food index starting at 0. Define movement deltas for U, D, L, R.
  2. move(direction): Calculate the new head position by applying the direction delta.
  3. Check if the new head is out of bounds. If so, return -1.
  4. Check if the new head collides with the snake body (exists in the hash set and is not the current tail). If so, return -1.
  5. If there is food at the new head position, increment the food index (the tail stays, so the snake grows).
  6. Otherwise, remove the tail from the deque and the hash set (the snake moves without growing).
  7. Add the new head to the front of the deque and to the hash set.
  8. Return the current score (snake length minus 1).

Complexity

  • Time Complexity:

    • The time complexity of the move function is O(1).
    • The time taken to calculate bites_itself is constant since we are using a dictionary to search for the element.
    • The time taken to add and remove an element from the queue is also constant.

  • Space Complexity: O(W × H + N)

    • O(N) is used by the food data structure.
    • O(W × H) is used by the snake and the snake_set data structures. At most, we can have snake that occupies all the cells of the grid.

Where W represents the width of the grid, H represents the height of the grid, and N represents the number of food items in the list.

Things to watch for

Confusing Width and Height with Row and Column

The grid is defined as width x height, but positions are given as [row, col] where row corresponds to height and column corresponds to width. Mixing these up causes incorrect boundary checks.

Not Excluding Tail When Checking Self-Collision

When the snake moves without eating, the tail vacates its position. The new head can legally occupy the old tail position. Failing to exclude the tail from collision detection causes false game-overs.

Wrong Order of Operations When Eating Food

When eating food, you must not remove the tail (so the snake grows). When not eating, you must remove the tail before adding the new head. Getting this order wrong causes the snake to grow incorrectly or the set to become inconsistent.

Python code example

from typing import List
import collections

class SnakeGame:

    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.snake = collections.deque([(0,0)])    # snake head is at the front
        self.snake_set = {(0,0) : 1}
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0
        self.movement = {'U': [-1, 0], 'L': [0, -1], 'R': [0, 1], 'D': [1, 0]}


    def move(self, direction: str) -> int:
        newHead = (self.snake[0][0] + self.movement[direction][0],
                   self.snake[0][1] + self.movement[direction][1])

        # Boundary conditions.
        crosses_boundary1 = newHead[0] < 0 or newHead[0] >= self.height
        crosses_boundary2 = newHead[1] < 0 or newHead[1] >= self.width

        # Checking if the snake bites itself.
        bites_itself = newHead in self.snake_set and newHead != self.snake[-1]

        # If any of the terminal conditions are satisfied, then we exit with rcode -1.
        if crosses_boundary1 or crosses_boundary2 or bites_itself:
            return -1

        # Note the food list could be empty at this point.
        next_food_item = self.food[self.food_index] if self.food_index < len(self.food) else None

        # If there's an available food item and it is on the cell occupied by the snake after the move, eat it
        if self.food_index < len(self.food) and \
            next_food_item[0] == newHead[0] and \
                next_food_item[1] == newHead[1]:  # eat food
            self.food_index += 1
        else:    # not eating food: delete tail
            tail = self.snake.pop()
            del self.snake_set[tail]

        # A new head always gets added
        self.snake.appendleft(newHead)

        # Also add the head to the set
        self.snake_set[newHead] = 1

        return len(self.snake) - 1

C++ code example

class SnakeGame {
    unordered_set<string> snakeSet;
    deque<pair<int, int>> snake;
    vector<vector<int>> food;
    int foodIndex;
    int width;
    int height;

    string pairToString(int row, int col) {
        return to_string(row) + "," + to_string(col);
    }

public:
    SnakeGame(int width, int height, vector<vector<int>>& food) {
        this->width = width;
        this->height = height;
        this->food = food;
        this->foodIndex = 0;
        this->snakeSet.insert(pairToString(0, 0)); // initially at [0][0]
        this->snake.push_back({0, 0});
    }

    int move(string direction) {
        pair<int, int> snakeCell = this->snake.front();
        int newHeadRow = snakeCell.first;
        int newHeadColumn = snakeCell.second;

        if (direction == "U") {
            newHeadRow--;
        } else if (direction == "D") {
            newHeadRow++;
        } else if (direction == "L") {
            newHeadColumn--;
        } else if (direction == "R") {
            newHeadColumn++;
        }

        pair<int, int> newHead = {newHeadRow, newHeadColumn};
        pair<int, int> currentTail = this->snake.back();

        // Boundary conditions.
        bool crossesBoundary1 = newHeadRow < 0 || newHeadRow >= this->height;
        bool crossesBoundary2 = newHeadColumn < 0 || newHeadColumn >= this->width;

        // Checking if the snake bites itself.
        bool bitesItself = this->snakeSet.count(pairToString(newHeadRow, newHeadColumn)) &&
                          !(newHead.first == currentTail.first && newHead.second == currentTail.second);

        // If any of the terminal conditions are satisfied, then we exit with rcode -1.
        if (crossesBoundary1 || crossesBoundary2 || bitesItself) {
            return -1;
        }

        // If there's an available food item and it is on the cell occupied by the snake after the move,
        // eat it.
        if ((this->foodIndex < this->food.size())
            && (this->food[this->foodIndex][0] == newHeadRow)
            && (this->food[this->foodIndex][1] == newHeadColumn)) {
            this->foodIndex++;
        } else {
            this->snake.pop_back();
            this->snakeSet.erase(pairToString(currentTail.first, currentTail.second));
        }

        // A new head always gets added
        this->snake.push_front(newHead);

        // Also add the head to the set
        this->snakeSet.insert(pairToString(newHeadRow, newHeadColumn));

        return this->snake.size() - 1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations