Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

353. Design Snake Game - Leetcode Solution

Code 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.snake = deque([(0, 0)])  # head at the right end
        self.snake_set = set([(0, 0)])
        self.dirs = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}

    def move(self, direction: str) -> int:
        head_row, head_col = self.snake[0]
        dr, dc = self.dirs[direction]
        new_row, new_col = head_row + dr, head_col + dc

        # Check wall collision
        if not (0 <= new_row < self.height and 0 <= new_col < self.width):
            return -1

        # Check self collision (remove tail from set if not eating food)
        tail = self.snake[-1]
        if self.food_index < len(self.food) and [new_row, new_col] == self.food[self.food_index]:
            self.food_index += 1
            grow = True
        else:
            grow = False
            self.snake_set.remove(tail)

        if (new_row, new_col) in self.snake_set:
            return -1

        self.snake.appendleft((new_row, new_col))
        self.snake_set.add((new_row, new_col))
        if not grow:
            self.snake.pop()
        else:
            # keep tail (snake grows)
            pass
        return len(self.snake) - 1
      
class SnakeGame {
public:
    int width, height, foodIndex;
    vector<vector<int>> food;
    deque<pair<int, int>> snake;
    unordered_set<int> snakeSet;

    SnakeGame(int width, int height, vector<vector<int>>& food) {
        this->width = width;
        this->height = height;
        this->food = food;
        foodIndex = 0;
        snake.push_back({0, 0});
        snakeSet.insert(0);
    }

    int move(string direction) {
        int dr = 0, dc = 0;
        if (direction == "U") dr = -1;
        else if (direction == "D") dr = 1;
        else if (direction == "L") dc = -1;
        else if (direction == "R") dc = 1;

        int headRow = snake.front().first, headCol = snake.front().second;
        int newRow = headRow + dr, newCol = headCol + dc;

        // Wall collision
        if (newRow < 0 || newRow >= height || newCol < 0 || newCol >= width) return -1;

        int tailRow = snake.back().first, tailCol = snake.back().second;
        int newPos = newRow * width + newCol;
        int tailPos = tailRow * width + tailCol;

        bool grow = false;
        if (foodIndex < food.size() && newRow == food[foodIndex][0] && newCol == food[foodIndex][1]) {
            grow = true;
            foodIndex++;
        } else {
            snakeSet.erase(tailPos);
        }

        if (snakeSet.count(newPos)) return -1;

        snake.push_front({newRow, newCol});
        snakeSet.insert(newPos);
        if (!grow) {
            snake.pop_back();
        }
        return snake.size() - 1;
    }
};
      
import java.util.*;

class SnakeGame {
    int width, height, foodIndex;
    int[][] food;
    Deque<int[]> snake;
    Set<Integer> snakeSet;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        foodIndex = 0;
        snake = new LinkedList<>();
        snake.addFirst(new int[]{0, 0});
        snakeSet = new HashSet<>();
        snakeSet.add(0);
    }

    public int move(String direction) {
        int dr = 0, dc = 0;
        if (direction.equals("U")) dr = -1;
        else if (direction.equals("D")) dr = 1;
        else if (direction.equals("L")) dc = -1;
        else if (direction.equals("R")) dc = 1;

        int[] head = snake.peekFirst();
        int newRow = head[0] + dr, newCol = head[1] + dc;

        if (newRow < 0 || newRow >= height || newCol < 0 || newCol >= width) return -1;

        int tailRow = snake.peekLast()[0], tailCol = snake.peekLast()[1];
        int newPos = newRow * width + newCol;
        int tailPos = tailRow * width + tailCol;

        boolean grow = false;
        if (foodIndex < food.length && newRow == food[foodIndex][0] && newCol == food[foodIndex][1]) {
            grow = true;
            foodIndex++;
        } else {
            snakeSet.remove(tailPos);
        }

        if (snakeSet.contains(newPos)) return -1;

        snake.addFirst(new int[]{newRow, newCol});
        snakeSet.add(newPos);
        if (!grow) {
            snake.pollLast();
        }
        return snake.size() - 1;
    }
}
      
class SnakeGame {
    constructor(width, height, food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.foodIndex = 0;
        this.snake = [[0, 0]]; // head at index 0
        this.snakeSet = new Set(['0,0']);
        this.dirs = {'U': [-1, 0], 'D': [1, 0], 'L': [0, -1], 'R': [0, 1]};
    }

    move(direction) {
        let [dr, dc] = this.dirs[direction];
        let [headRow, headCol] = this.snake[0];
        let newRow = headRow + dr, newCol = headCol + dc;

        // Wall collision
        if (newRow < 0 || newRow >= this.height || newCol < 0 || newCol >= this.width) return -1;

        let tail = this.snake[this.snake.length - 1];
        let grow = false;
        if (this.foodIndex < this.food.length && newRow === this.food[this.foodIndex][0] && newCol === this.food[this.foodIndex][1]) {
            this.foodIndex++;
            grow = true;
        } else {
            this.snakeSet.delete(tail.join(','));
        }

        if (this.snakeSet.has([newRow, newCol].join(','))) return -1;

        this.snake.unshift([newRow, newCol]);
        this.snakeSet.add([newRow, newCol].join(','));
        if (!grow) {
            this.snake.pop();
        }
        return this.snake.length - 1;
    }
}

Problem Description

You are asked to design a simple Snake game on a 2D grid. The snake starts at the top-left corner of the grid at position (0, 0). The grid has a specified width and height. There is a list of food positions that the snake can eat to grow longer. Each time the snake eats food, its length increases by one, and the next food appears. The snake moves according to a sequence of commands: 'U' (up), 'D' (down), 'L' (left), or 'R' (right).

The game ends when the snake either runs into the wall or into itself. After each move, you must return the score, which is the number of food items eaten so far, or -1 if the game is over. The snake cannot move outside the grid or into its own body, except for the tail position if the tail is moving forward (since the tail leaves that spot).

Key constraints:

  • Food must be eaten in order, and only one food item is present at a time.
  • The snake cannot reuse positions already occupied by its body unless the tail is moving away from that position in the same move.
  • Each move must be processed efficiently, as the game may have many moves.

Thought Process

To solve this problem, we need to simulate the snake's movement while efficiently checking for collisions with the wall and itself. The naive approach would be to scan the entire snake's body to check for collisions after each move, but this would be too slow as the snake grows longer.

Therefore, we look for ways to optimize:

  • We need a quick way to check if the snake's new head position collides with its body.
  • We must manage the snake's body so we can efficiently add a new head and remove the tail as it moves.
  • We also need to handle the special case where the snake eats food and thus grows (the tail does not move in that step).
Using a queue (or deque) to represent the snake's body and a hash set for fast collision checks is a natural fit. The queue allows us to easily add the new head and remove the old tail, while the set allows O(1) collision detection.

Solution Approach

Let's break down the solution step by step:

  1. Data Structures:
    • Use a deque (double-ended queue) to store the positions of the snake's body in order, with the head at one end and the tail at the other.
    • Use a hash set to store the positions occupied by the snake for O(1) collision checks.
  2. Moving the Snake:
    • Calculate the new head position based on the direction.
    • Check if the new head position is outside the grid (wall collision).
    • Check if the new head position is in the snake's body (self-collision), except for the tail if the tail is moving away in this move.
  3. Eating Food:
    • If the new head position matches the next food, the snake grows: do not remove the tail from the deque or set.
    • If not eating, remove the tail position from the deque and set before checking for self-collision, since the tail is moving away.
  4. Updating State:
    • Add the new head position to both the deque and the set.
    • Return the score (snake's length minus one, since the initial length is one).

This design ensures all operations are efficient, and the game simulation is accurate.

Example Walkthrough

Suppose we have a 3x3 grid (width = 3, height = 3) and food at positions [[2,0],[0,0],[0,2],[2,2]].

  1. Initial State: Snake at (0,0). Score: 0.
  2. Move 'D': Snake moves to (1,0). No food. Score: 0.
  3. Move 'D': Snake moves to (2,0). Eats food. Snake grows to length 2. Score: 1.
  4. Move 'R': Snake moves to (2,1). No food. Tail moves forward. Score: 1.
  5. Move 'U': Snake moves to (1,1). No food. Score: 1.
  6. Move 'U': Snake moves to (0,1). No food. Score: 1.
  7. Move 'L': Snake moves to (0,0). Eats food. Snake grows to length 3. Score: 2.

At each step, we check for wall collisions, self-collisions, and whether the snake eats food, updating the state accordingly.

Time and Space Complexity

Brute-force approach: If we scanned the snake's entire body for collisions after every move, each move would be O(N) where N is the snake's length. As the snake grows, this becomes inefficient.

Optimized approach: By using a set for the snake's positions, checking for self-collision is O(1). Adding/removing from deque and set is also O(1). Thus, each move is processed in O(1) time.

Space complexity: Both the deque and set store each segment of the snake, so space is O(N), where N is the maximum possible length of the snake (up to the grid size).

Summary

We designed an efficient simulation of the Snake game using a double-ended queue to represent the snake's body and a hash set for fast collision detection. By carefully updating these structures as the snake moves and grows, we ensure all operations are fast and the game rules are enforced. This approach avoids the inefficiency of scanning the whole snake each time, making the solution elegant and scalable for large grids and long snakes.