Facebook Pixel

353. Design Snake Game 🔒

MediumDesignQueueArrayHash TableSimulation
Leetcode Link

Problem Description

This problem asks you to implement a Snake game with the following rules and requirements:

Game Setup:

  • The game is played on a screen with dimensions height x width
  • The snake starts at position (0, 0) (top-left corner) with length 1
  • Food items are provided as an array where food[i] = (ri, ci) represents the row and column position of the i-th food piece

Game Mechanics:

  • When the snake eats food, both its length and the game score increase by 1
  • Food appears one at a time - the next food item only appears after the current one is eaten
  • Food is guaranteed to never appear on a position occupied by the snake

Game Over Conditions:

  • The snake moves out of bounds (hits a wall)
  • The snake's head collides with its own body after moving

Implementation Requirements:

You need to implement a SnakeGame class with two methods:

  1. SnakeGame(int width, int height, int[][] food): Constructor that initializes the game with the screen dimensions and food positions

  2. int move(String direction): Processes one move in the given direction ("U" for up, "D" for down, "L" for left, "R" for right) and returns:

    • The current score if the move is valid
    • -1 if the game is over (snake hits wall or itself)

The key challenge is tracking the snake's body positions efficiently while handling the growth when eating food and checking for self-collision. The snake moves by adding a new head position in the direction of movement and removing the tail (unless food is eaten, in which case the tail remains to increase length).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight for solving this problem is understanding how a snake moves in the classic game. When a snake moves, it doesn't actually move every segment - instead, it adds a new head in the direction of movement and removes its tail. This creates the illusion of movement while being computationally efficient.

Think about it this way: if the snake is 5 units long and moves right, we don't need to update all 5 positions. We just:

  1. Add a new head to the right of the current head
  2. Remove the tail (unless food was just eaten)

This observation leads us to use a deque (double-ended queue) data structure, which allows efficient addition at the front (new head) and removal from the back (tail).

For collision detection, we need to quickly check if a position is occupied by the snake's body. A set is perfect for this - it gives us O(1) lookup time to check if the new head position would collide with any part of the body.

The special case of eating food is handled elegantly: when the snake's new head position matches the current food position, we simply skip removing the tail. This naturally increases the snake's length by one unit.

The order of operations is crucial to avoid false collisions:

  1. First, calculate where the new head would be
  2. Check if it's out of bounds (wall collision)
  3. Check if it's food - if yes, eat it (increment score and food index)
  4. If not food, remove the tail from both the deque and the set
  5. Check if the new head position collides with the body (now that tail is removed if needed)
  6. Finally, add the new head to both the deque and the set

This sequence ensures that the snake can move into the space its tail just vacated, which is a valid move in the game.

Solution Approach

The implementation uses a deque and a set to efficiently manage the snake's movement and collision detection.

Data Structures:

  • self.q: A deque that stores the snake's body positions as (row, column) tuples, with the head at index 0
  • self.vis: A set that stores all positions occupied by the snake for O(1) collision checking
  • self.food: Array of food positions
  • self.idx: Current food index to track which food item should appear next
  • self.score: Current game score

Initialization (__init__ method):

self.q = deque([(0, 0)])  # Snake starts at top-left
self.vis = {(0, 0)}       # Mark initial position as occupied
self.score = 0            # Initial score
self.idx = 0              # Start with first food item

Move Implementation (move method):

  1. Get current head position and calculate new position:

    i, j = self.q[0]  # Current head position
    x, y = i, j       # New position (to be updated based on direction)
  2. Update position based on direction using pattern matching:

    match direction:
        case "U": x -= 1  # Move up (decrease row)
        case "D": x += 1  # Move down (increase row)
        case "L": y -= 1  # Move left (decrease column)
        case "R": y += 1  # Move right (increase column)
  3. Check boundary collision:

    if x < 0 or x >= self.m or y < 0 or y >= self.n:
        return -1  # Game over - hit wall
  4. Handle food consumption or normal movement:

    if (self.idx < len(self.food) and 
        x == self.food[self.idx][0] and 
        y == self.food[self.idx][1]):
        # Food eaten - increase score and move to next food
        self.score += 1
        self.idx += 1
    else:
        # No food - remove tail (snake doesn't grow)
        self.vis.remove(self.q.pop())
  5. Check self-collision:

    if (x, y) in self.vis:
        return -1  # Game over - snake hit itself
  6. Add new head position:

    self.q.appendleft((x, y))  # Add to front of deque
    self.vis.add((x, y))       # Mark position as occupied
    return self.score

Time Complexity:

  • move(): O(1) for all operations (deque append/pop, set add/remove/lookup)

Space Complexity:

  • O(N) where N is the maximum length of the snake (at most width × height)

The elegance of this solution lies in how the deque naturally models the snake's movement pattern, while the set provides efficient collision detection. The careful ordering of operations ensures correct game logic, particularly allowing the snake to move into the space its tail just vacated.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with a 3×3 grid and food at positions [(1,2), (2,0)].

Initial Setup:

  • Grid: 3×3 (height=3, width=3)
  • Snake starts at (0,0) with length 1
  • Food sequence: [(1,2), (2,0)]
Initial state:
[S][ ][ ]   S = Snake head
[ ][ ][F]   F = Food at (1,2)
[ ][ ][ ]   Score = 0

Move 1: move("R") - Move right

  1. Current head: (0,0), calculate new position: (0,1)
  2. Check bounds: 0≤0<3 and 0≤1<3 ✓
  3. Not food position, remove tail from (0,0)
  4. Check collision: (0,1) not in body ✓
  5. Add new head at (0,1)
[ ][S][ ]   Score = 0
[ ][ ][F]   
[ ][ ][ ]   

Move 2: move("D") - Move down

  1. Current head: (0,1), new position: (1,1)
  2. Check bounds: ✓
  3. Not food, remove tail
  4. No collision ✓
  5. Add new head at (1,1)
[ ][ ][ ]   Score = 0
[ ][S][F]   
[ ][ ][ ]   

Move 3: move("R") - Move right (eat food!)

  1. Current head: (1,1), new position: (1,2)
  2. Check bounds: ✓
  3. Food at (1,2)! Score increases, don't remove tail
  4. No collision ✓
  5. Add new head at (1,2)
[ ][ ][ ]   Score = 1
[ ][B][S]   B = Body, S = Head
[F][ ][ ]   Next food appears at (2,0)
Snake length = 2

Move 4: move("D") - Move down

  1. Current head: (1,2), new position: (2,2)
  2. Check bounds: ✓
  3. Not food, remove tail from (1,1)
  4. No collision ✓
  5. Add new head at (2,2)
[ ][ ][ ]   Score = 1
[ ][ ][B]   
[F][ ][S]   Snake: (2,2)→(1,2)

Move 5: move("L") - Move left

  1. Current head: (2,2), new position: (2,1)
  2. Check bounds: ✓
  3. Not food, remove tail from (1,2)
  4. No collision ✓
  5. Add new head at (2,1)
[ ][ ][ ]   Score = 1
[ ][ ][ ]   
[F][S][B]   Snake: (2,1)→(2,2)

Move 6: move("L") - Move left (eat food!)

  1. Current head: (2,1), new position: (2,0)
  2. Check bounds: ✓
  3. Food at (2,0)! Score increases, don't remove tail
  4. No collision ✓
  5. Add new head at (2,0)
[ ][ ][ ]   Score = 2
[ ][ ][ ]   
[S][B][B]   Snake: (2,0)→(2,1)→(2,2)
             Length = 3

Move 7: move("U") - Move up (collision example)

  1. Current head: (2,0), new position: (1,0)
  2. Check bounds: ✓
  3. Not food, remove tail from (2,2)
  4. No collision ✓
  5. Add new head at (1,0)
[ ][ ][ ]   Score = 2
[S][ ][ ]   
[B][B][ ]   Snake: (1,0)→(2,0)→(2,1)

Move 8: move("U") - Move up (wall collision)

  1. Current head: (1,0), new position: (0,0)
  2. Check bounds: ✓
  3. Not food, remove tail from (2,1)
  4. No collision ✓
  5. Add new head at (0,0)
[S][ ][ ]   Score = 2
[B][ ][ ]   
[B][ ][ ]   Snake: (0,0)→(1,0)→(2,0)

Move 9: move("U") - Invalid move (hits wall)

  1. Current head: (0,0), new position: (-1,0)
  2. Check bounds: -1 < 0 - Out of bounds!
  3. Return -1 (Game Over)

This example demonstrates:

  • Normal movement (removing tail)
  • Food consumption (keeping tail to grow)
  • Boundary checking
  • How the deque and set work together to track the snake efficiently

Solution Implementation

1from collections import deque
2from typing import List
3
4class SnakeGame:
5    def __init__(self, width: int, height: int, food: List[List[int]]):
6        """
7        Initialize the snake game with given dimensions and food positions.
8      
9        Args:
10            width: Width of the game board
11            height: Height of the game board
12            food: List of food positions [row, col]
13        """
14        self.height = height
15        self.width = width
16        self.food = food
17        self.score = 0
18        self.food_index = 0
19      
20        # Snake body represented as deque with head at front
21        self.snake = deque([(0, 0)])
22      
23        # Set to track occupied positions for O(1) collision detection
24        self.occupied_positions = {(0, 0)}
25
26    def move(self, direction: str) -> int:
27        """
28        Move the snake in the specified direction.
29      
30        Args:
31            direction: Direction to move ('U', 'D', 'L', 'R')
32          
33        Returns:
34            Score after the move, or -1 if game over
35        """
36        # Get current head position
37        current_row, current_col = self.snake[0]
38        new_row, new_col = current_row, current_col
39      
40        # Calculate new head position based on direction
41        if direction == "U":
42            new_row -= 1
43        elif direction == "D":
44            new_row += 1
45        elif direction == "L":
46            new_col -= 1
47        elif direction == "R":
48            new_col += 1
49      
50        # Check if new position is out of bounds
51        if new_row < 0 or new_row >= self.height or new_col < 0 or new_col >= self.width:
52            return -1
53      
54        # Check if food is eaten at new position
55        if (self.food_index < len(self.food) and 
56            new_row == self.food[self.food_index][0] and 
57            new_col == self.food[self.food_index][1]):
58            # Food eaten: increase score and move to next food
59            self.score += 1
60            self.food_index += 1
61        else:
62            # No food eaten: remove tail
63            tail = self.snake.pop()
64            self.occupied_positions.remove(tail)
65      
66        # Check if new head position collides with snake body
67        if (new_row, new_col) in self.occupied_positions:
68            return -1
69      
70        # Add new head position
71        self.snake.appendleft((new_row, new_col))
72        self.occupied_positions.add((new_row, new_col))
73      
74        return self.score
75
1class SnakeGame {
2    // Grid dimensions
3    private int rows;
4    private int cols;
5    // Food positions array
6    private int[][] foodPositions;
7    // Current score (number of food items eaten)
8    private int score;
9    // Index of next food item to be eaten
10    private int foodIndex;
11    // Deque to store snake body positions (encoded as single integers)
12    private Deque<Integer> snakeBody;
13    // Set to quickly check if a position is occupied by snake body
14    private Set<Integer> occupiedPositions;
15
16    /**
17     * Initialize the game with grid dimensions and food positions
18     * @param width Grid width (number of columns)
19     * @param height Grid height (number of rows)
20     * @param food Array of food positions, each as [row, col]
21     */
22    public SnakeGame(int width, int height, int[][] food) {
23        this.rows = height;
24        this.cols = width;
25        this.foodPositions = food;
26        this.score = 0;
27        this.foodIndex = 0;
28        this.snakeBody = new ArrayDeque<>();
29        this.occupiedPositions = new HashSet<>();
30      
31        // Initialize snake at position (0, 0)
32        int startPosition = encodePosition(0, 0);
33        snakeBody.offer(startPosition);
34        occupiedPositions.add(startPosition);
35    }
36
37    /**
38     * Move the snake in the specified direction
39     * @param direction Direction to move: "U" (up), "D" (down), "L" (left), "R" (right)
40     * @return Current score after move, or -1 if game over
41     */
42    public int move(String direction) {
43        // Get current head position
44        int currentHead = snakeBody.peekFirst();
45        int currentRow = currentHead / cols;
46        int currentCol = currentHead % cols;
47      
48        // Calculate new head position based on direction
49        int newRow = currentRow;
50        int newCol = currentCol;
51      
52        if ("U".equals(direction)) {
53            newRow--;
54        } else if ("D".equals(direction)) {
55            newRow++;
56        } else if ("L".equals(direction)) {
57            newCol--;
58        } else {  // "R"
59            newCol++;
60        }
61      
62        // Check if new position is out of bounds
63        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) {
64            return -1;  // Game over - hit wall
65        }
66      
67        // Check if food is at the new position
68        boolean foodEaten = false;
69        if (foodIndex < foodPositions.length && 
70            newRow == foodPositions[foodIndex][0] && 
71            newCol == foodPositions[foodIndex][1]) {
72            // Food eaten - increase score and move to next food
73            score++;
74            foodIndex++;
75            foodEaten = true;
76        } else {
77            // No food eaten - remove tail to maintain snake length
78            int tail = snakeBody.pollLast();
79            occupiedPositions.remove(tail);
80        }
81      
82        // Check if new head position collides with snake body
83        int newHeadEncoded = encodePosition(newRow, newCol);
84        if (occupiedPositions.contains(newHeadEncoded)) {
85            return -1;  // Game over - snake hit itself
86        }
87      
88        // Add new head position
89        snakeBody.offerFirst(newHeadEncoded);
90        occupiedPositions.add(newHeadEncoded);
91      
92        return score;
93    }
94
95    /**
96     * Encode a 2D position (row, col) into a single integer
97     * @param row Row index
98     * @param col Column index
99     * @return Encoded position as single integer
100     */
101    private int encodePosition(int row, int col) {
102        return row * cols + col;
103    }
104}
105
106/**
107 * Your SnakeGame object will be instantiated and called as such:
108 * SnakeGame obj = new SnakeGame(width, height, food);
109 * int param_1 = obj.move(direction);
110 */
111
1class SnakeGame {
2public:
3    /**
4     * Initialize the snake game with given board dimensions and food positions
5     * @param width: Width of the game board
6     * @param height: Height of the game board  
7     * @param food: List of food positions [row, col]
8     */
9    SnakeGame(int width, int height, vector<vector<int>>& food) {
10        boardHeight = height;
11        boardWidth = width;
12        this->foodPositions = food;
13        currentScore = 0;
14        nextFoodIndex = 0;
15      
16        // Initialize snake at position (0, 0)
17        snakeBody.push_back(0);
18        occupiedCells.insert(0);
19    }
20
21    /**
22     * Move the snake in the specified direction
23     * @param direction: Direction to move ("U", "D", "L", "R")
24     * @return: Current score after move, or -1 if game over
25     */
26    int move(string direction) {
27        // Get current head position
28        int headPosition = snakeBody.front();
29        int currentRow = headPosition / boardWidth;
30        int currentCol = headPosition % boardWidth;
31      
32        // Calculate new head position based on direction
33        int newRow = currentRow;
34        int newCol = currentCol;
35      
36        if (direction == "U") {
37            newRow--;
38        } else if (direction == "D") {
39            newRow++;
40        } else if (direction == "L") {
41            newCol--;
42        } else {  // direction == "R"
43            newCol++;
44        }
45      
46        // Check if snake hits the wall
47        if (newRow < 0 || newRow >= boardHeight || newCol < 0 || newCol >= boardWidth) {
48            return -1;
49        }
50      
51        // Check if snake eats food
52        if (nextFoodIndex < foodPositions.size() && 
53            newRow == foodPositions[nextFoodIndex][0] && 
54            newCol == foodPositions[nextFoodIndex][1]) {
55            // Snake grows - increase score and move to next food
56            currentScore++;
57            nextFoodIndex++;
58        } else {
59            // Snake moves without growing - remove tail
60            int tailPosition = snakeBody.back();
61            snakeBody.pop_back();
62            occupiedCells.erase(tailPosition);
63        }
64      
65        // Calculate new head position as encoded value
66        int newHeadPosition = encodePosition(newRow, newCol);
67      
68        // Check if snake hits itself
69        if (occupiedCells.count(newHeadPosition)) {
70            return -1;
71        }
72      
73        // Add new head to snake
74        snakeBody.push_front(newHeadPosition);
75        occupiedCells.insert(newHeadPosition);
76      
77        return currentScore;
78    }
79
80private:
81    int boardHeight;                           // Height of the game board
82    int boardWidth;                            // Width of the game board
83    vector<vector<int>> foodPositions;         // List of food positions
84    int currentScore;                           // Current game score
85    int nextFoodIndex;                          // Index of next food to eat
86    deque<int> snakeBody;                       // Snake body positions (head at front)
87    unordered_set<int> occupiedCells;          // Set of cells occupied by snake
88  
89    /**
90     * Encode 2D position (row, col) into a single integer
91     * @param row: Row position
92     * @param col: Column position
93     * @return: Encoded position value
94     */
95    int encodePosition(int row, int col) {
96        return row * boardWidth + col;
97    }
98};
99
100/**
101 * Your SnakeGame object will be instantiated and called as such:
102 * SnakeGame* obj = new SnakeGame(width, height, food);
103 * int param_1 = obj->move(direction);
104 */
105
1// Game board dimensions
2let boardHeight: number;
3let boardWidth: number;
4
5// Food positions array
6let foodPositions: number[][];
7
8// Current score
9let currentScore: number;
10
11// Current food index
12let currentFoodIndex: number;
13
14// Snake body queue (stores positions as encoded values)
15let snakeQueue: number[];
16
17// Set to track occupied positions for collision detection
18let occupiedPositions: Set<number>;
19
20/**
21 * Initializes the Snake Game
22 * @param width - The width of the game board
23 * @param height - The height of the game board  
24 * @param food - Array of food positions [row, col]
25 */
26function SnakeGame(width: number, height: number, food: number[][]): void {
27    boardHeight = height;
28    boardWidth = width;
29    foodPositions = food;
30    currentScore = 0;
31    currentFoodIndex = 0;
32  
33    // Initialize snake at position (0, 0) encoded as 0
34    snakeQueue = [0];
35    occupiedPositions = new Set([0]);
36}
37
38/**
39 * Moves the snake in the specified direction
40 * @param direction - Direction to move ('U', 'D', 'L', 'R')
41 * @returns Current score if move is valid, -1 if game over
42 */
43function move(direction: string): number {
44    // Get current head position
45    const headPosition = snakeQueue[0];
46    const currentRow = Math.floor(headPosition / boardWidth);
47    const currentCol = headPosition % boardWidth;
48  
49    // Calculate new position based on direction
50    let newRow = currentRow;
51    let newCol = currentCol;
52  
53    if (direction === 'U') {
54        newRow--;
55    } else if (direction === 'D') {
56        newRow++;
57    } else if (direction === 'L') {
58        newCol--;
59    } else {
60        newCol++;
61    }
62  
63    // Check if new position is out of bounds
64    if (newRow < 0 || newRow >= boardHeight || newCol < 0 || newCol >= boardWidth) {
65        return -1;
66    }
67  
68    // Check if food is at the new position
69    if (currentFoodIndex < foodPositions.length &&
70        newRow === foodPositions[currentFoodIndex][0] &&
71        newCol === foodPositions[currentFoodIndex][1]) {
72        // Eat food: increase score and move to next food
73        currentScore++;
74        currentFoodIndex++;
75    } else {
76        // No food: remove tail (snake moves without growing)
77        const tailPosition = snakeQueue.pop()!;
78        occupiedPositions.delete(tailPosition);
79    }
80  
81    // Encode new head position
82    const newHeadPosition = newRow * boardWidth + newCol;
83  
84    // Check if snake collides with itself
85    if (occupiedPositions.has(newHeadPosition)) {
86        return -1;
87    }
88  
89    // Add new head position
90    snakeQueue.unshift(newHeadPosition);
91    occupiedPositions.add(newHeadPosition);
92  
93    return currentScore;
94}
95

Time and Space Complexity

Time Complexity:

  • __init__: O(1) - Initializes the game with constant time operations. Creating a deque with one element and a set with one element are both O(1) operations.
  • move: O(1) - Each move operation performs:
    • Direction calculation: O(1)
    • Boundary checking: O(1)
    • Food checking: O(1)
    • Adding/removing from deque: O(1) for both appendleft and pop
    • Adding/removing from set: O(1) average case for both operations
    • Checking membership in set: O(1) average case

Space Complexity:

  • O(W × H) in the worst case, where W is the width and H is the height of the game board.
  • The space is primarily used by:
    • self.q (deque): Can grow up to size W × H if the snake fills the entire board
    • self.vis (set): Maintains the same positions as the deque, so also up to W × H elements
    • self.food: O(F) where F is the number of food items, but this is typically much smaller than W × H
  • In practice, the space complexity is O(min(S, W × H)) where S is the current length of the snake, since the snake's body occupies S cells at any given time.

Common Pitfalls

1. Incorrect Order of Tail Removal and Self-Collision Check

The Pitfall: A critical bug occurs if you check for self-collision before removing the tail when the snake doesn't eat food. This creates a false collision when the snake moves into the space its tail is vacating.

Incorrect Implementation:

def move(self, direction: str) -> int:
    # Calculate new head position...
    new_row, new_col = ...
  
    # Check self-collision FIRST (WRONG!)
    if (new_row, new_col) in self.occupied_positions:
        return -1
  
    # Then handle food/tail removal
    if food_eaten:
        self.score += 1
    else:
        tail = self.snake.pop()
        self.occupied_positions.remove(tail)

Why It Fails: When the snake moves into its tail's current position (a valid move), the collision check happens before the tail is removed, causing a false game over.

Example Scenario:

  • Snake: [(1,1), (1,2), (2,2), (2,1)] forming a square
  • Move: "L" (left)
  • New head would be at (2,1) - currently the tail
  • If checked before tail removal: Game Over (incorrect!)
  • If tail removed first: Valid move

Correct Solution:

def move(self, direction: str) -> int:
    # Calculate new head position
    new_row, new_col = ...
  
    # Check boundary first
    if out_of_bounds:
        return -1
  
    # Remove tail BEFORE collision check (if no food)
    if food_eaten:
        self.score += 1
    else:
        tail = self.snake.pop()
        self.occupied_positions.remove(tail)
  
    # NOW check for self-collision
    if (new_row, new_col) in self.occupied_positions:
        return -1
  
    # Add new head
    self.snake.appendleft((new_row, new_col))
    self.occupied_positions.add((new_row, new_col))

2. Not Synchronizing Snake Body and Position Set

The Pitfall: Forgetting to update the occupied_positions set when modifying the snake deque leads to inconsistent state.

Common Mistakes:

  • Adding to deque but not to set
  • Removing from deque but not from set
  • Using list operations that bypass the set updates

Prevention: Always pair deque and set operations:

# Always together for adding
self.snake.appendleft(new_pos)
self.occupied_positions.add(new_pos)

# Always together for removing
removed = self.snake.pop()
self.occupied_positions.remove(removed)

3. Misunderstanding Food Index Bounds

The Pitfall: Not properly checking if all food has been consumed before accessing self.food[self.food_index].

Incorrect:

# This will cause IndexError when food_index >= len(food)
if (new_row == self.food[self.food_index][0] and 
    new_col == self.food[self.food_index][1]):

Correct:

if (self.food_index < len(self.food) and 
    new_row == self.food[self.food_index][0] and 
    new_col == self.food[self.food_index][1]):

The short-circuit evaluation ensures we don't access an invalid index when all food is consumed.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More