353. Design Snake Game

MediumDesignQueueArrayHash TableSimulation

Problem Description

The LeetCode problem presents us with a classic game of Snake, where the objective is to control a snake that moves around a grid, eats food, and grows in length with each piece of food it consumes. The game stops if the snake either runs into the wall or itself. We're asked to design the game logic for a snake initially of length 1 unit, starting from the top-left corner of the grid with dimensions height x width.

The grid functions like a 2D array where the food items are coordinates listed in the food array. The snake moves in one of four directions each turn: up (U), down (D), left (L), or right (R). The game scores a point when the snake eats a piece of food, which involves moving to the same coordinate location as the next item in the food array. Food items appear sequentially, with the next item making its appearance only after the current one has been eaten. The game is over if the snake tries to move beyond the boundary of the grid or into a space occupied by its body.

The objective is to implement the SnakeGame class with:

A constructor SnakeGame(int width, int height, int[][] food) which initializes the game with the screen size and the food positions.
A method int move(String direction) to move the snake in the requested direction and return the game's score or -1 if the game is over.

Intuition

A smart approach to this problem involves simulating the snake's movement and food consumption on a virtual grid. We need to track the snake's segments and manage our game's state in response to each move call representing the snake's new direction. Given that the snake moves one unit per turn, we can represent its body as a queue, specifically a deque (double-ended queue), where we add the head to one end and remove the tail from the other end each time the snake moves.

To implement this, we require a system to check whether the new position after a move is valid (not hitting walls or its own body), and a way to check whether the snake has reached food.

The solution consists of the following steps:

Initialize the game state with a deque to represent the snake's body, starting with just the head at the cell (0,0). We'll also use a set for O(1) lookups to ensure the snake does not collide with itself.
Upon each move action, calculate the snake's new head position.
If this position is off-grid, the game is over.
If the new position has food, update the score, and increase the food index to the next food item without removing the current tail segment. This simulates the growth of the snake.
If there is no food, remove the tail segment (pop from the deque), as we're moving without growing.
Check if the new position would cause a self-collision. If so, the game is over.
If the snake survives, update the deque and the set to include the new head position and return the current score.

The usage of a deque allows us to efficiently handle the snake's body segments without the need to shift elements - operations are O(1) for adding/removing from both ends. The set facilitates O(1) lookups to detect self-collisions.

Learn more about Queue patterns.

Solution Approach

The solution to this Snake game problem uses a combination of a queue, specifically a deque (double-ended queue), and a set for efficient operations and checks. Here's a step-by-step approach to the implementation:

Initialization (__init__): Set up the initial state in the constructor. The snake's body is represented by a deque called q with one element, (0, 0), the initial head position. A set called vis (short for visited) stores the same position to keep track of the cells occupied by the snake (this helps with collision checks). The game's score, the index of the current food item to be eaten (idx), the list of food coordinates food, and the dimensions of the grid are also initialized here.
Move Method (move):
1. Extract the current head position of the snake (i, j) from the front of the deque.
2. Based on the direction provided, calculate the new head position (x, y). Utilizing Python's match-case allows a clear syntax to adjust the coordinates for each possible direction.
3. Check if the new position is outside the bounds of the grid (x < 0 or x >= self.m or y < 0 or y >= self.n). If so, return -1 to signify the game is over.
4. Determine if the new position contains food by comparing it to the current food item at index idx. If it does, increase score by 1 and increment idx to point to the next food item but do not pop the tail from the deque because we want the snake's length to increase.
5. If the new position doesn't have food, remove the tail end of the snake (pop from the deque) and remove the corresponding position from the vis set because the snake moves forward without growing.
6. If the new position is in the vis set (meaning the new head position is a cell already occupied by its body), return -1 to indicate a self-collision.
7. Otherwise, add the new position to the front of the deque and add it to the vis set, representing the snake moving forward.
8. Return the current score.

Algorithmic Complexity:

The operations deque.appendleft(), deque.pop(), set.add(), and set.remove() are all O(1), meaning they have a constant time complexity per move.
Checking if the new head position collides with the body ((x, y) in self.vis) is also O(1) thanks to the set data structure.

Data Structures:

Deque: Chosen for representing the snake's body because it allows for appending and popping at both ends efficiently.
Set: Chosen for O(1) collision checks with the snake's body.

By judiciously combining these data structures and careful handling of edge cases, the reference solution simulates the game of Snake correctly and efficiently.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

In this walkthrough, we'll follow a simple example to demonstrate how the solution approach is implemented when a SnakeGame instance is created and several moves are made. Assume we have a 3x3 grid (width = 3, height = 3) and two food items at positions [[1, 2], [2, 2]].

Initialization: We instantiate the SnakeGame with a width of 3, a height of 3, and a food list. The snake starts at (0, 0) (top-left corner).
First Move (Right - 'R'): The snake's head is currently (0, 0). With this move to the right, the new head position will be (0, 1). Since this is neither off the grid nor does it have food, the tail stays therefore, we remove the tail from the deque (0,0), and vis set. We add the new head (0, 1) to the q and vis. The game’s score remains 0.
Second Move (Right - 'R'): Now, the head moves further right to (0, 2). At this position, there is food ([1, 2] is our first food item). The snake grows and scores a point. We add (0, 2) to the q and vis. We do not remove the tail because the snake has grown. The score is now 1, and the food index (idx) increments to point to the next food at [2, 2].
Third Move (Down - 'D'): The snake moves down to (1, 2). This space doesn't have food because we've already consumed the food here. We remove the tail from the q and the vis set. The tail was (0, 1); therefore, the snake's body now consists of the cells at (0, 2) and (1, 2). The score remains 1.
Fourth Move (Down - 'D'): The snake moves further down to (2, 2). This is where the second food item is located, so the snake grows again, scoring another point. We add (2, 2) to the q and vis. Again, we do not pop the tail. The game's score is now 2.
Fifth Move (Left - 'L'): If the snake attempts to move left, its new head position would be (2, 1) which doesn't result in a boundary collision or self-collision, and it does not contain food. Thus, we pop (0, 2) from the q and remove it from vis. The body now occupies cells (1, 2) and (2, 2). Head is added at (2, 1) and the game score is still 2.
Subsequent Movements: Any subsequent moves will follow the same logic about the grid boundaries, food presence, and self-collision checks, modifying the score, deque, and set accordingly. If a move results in a collision with a wall or the snake itself, the game would end, and -1 would be returned.

Following this logic properly simulates the snake's movement around the grid, ensuring efficient and correct behavior for the game.

Solution Implementation

1from collections import deque
2
3class SnakeGame:
4    def __init__(self, width: int, height: int, food: List[List[int]]):
5        # Initialize the game board with the given width and height
6        self.width = width
7        self.height = height
8      
9        # Load the food positions onto the game board
10        self.food = deque(food)
11      
12        # Initialize the score of the game as 0
13        self.score = 0
14      
15        # The snake's body is represented as a queue with initial position at the top-left
16        self.snake = deque([(0, 0)])
17      
18        # A set to keep track of all positions occupied by the snake
19        self.snake_positions = set([(0, 0)])
20
21    def move(self, direction: str) -> int:
22        # Get the snake's current head position
23        head_row, head_col = self.snake[0]
24      
25        # Move based on the provided direction
26        if direction == 'U':
27            head_row -= 1
28        elif direction == 'D':
29            head_row += 1
30        elif direction == 'L':
31            head_col -= 1
32        elif direction == 'R':
33            head_col += 1
34      
35        # Check if the new position is out of bounds
36        if head_row < 0 or head_row >= self.height or head_col < 0 or head_col >= self.width:
37            return -1
38      
39        # Check if the snake has moved to a cell containing food
40        if self.food and [head_row, head_col] == self.food[0]:
41            self.food.popleft()  # Eat the food
42            self.score += 1      # Increase the score
43        else:
44            # Remove the tail if no food is eaten
45            tail = self.snake.pop()
46            self.snake_positions.remove(tail)
47      
48        # Check if the snake crashes into itself
49        if (head_row, head_col) in self.snake_positions:
50            return -1
51      
52        # Add the new head position of the snake
53        self.snake.appendleft((head_row, head_col))
54        self.snake_positions.add((head_row, head_col))
55      
56        # Return the current score of the game
57        return self.score
58
59
60# Example of how to instantiate and use the class
61# game = SnakeGame(width, height, food)
62# score = game.move(direction)
63

1import java.util.ArrayDeque;
2import java.util.Deque;
3import java.util.HashSet;
4import java.util.Set;
5
6public class SnakeGame {
7
8    private int height;
9    private int width;
10    private int[][] food;
11    private int score;
12    private int foodIndex;
13    private Deque<Integer> snakeBody = new ArrayDeque<>();
14    private Set<Integer> visited = new HashSet<>();
15
16    // Constructor initializes the game with the width and height of the board and the food locations.
17    public SnakeGame(int width, int height, int[][] food) {
18        this.height = height;
19        this.width = width;
20        this.food = food;
21        snakeBody.offer(0); // Snake starts at the top-left corner (0,0)
22        visited.add(0); // Mark the start position as occupied
23    }
24
25    // Moves the snake in the given direction and returns the score.
26    public int move(String direction) {
27        int head = snakeBody.peekFirst();
28        int row = head / width, col = head % width;
29        int newRow = row, newCol = col;
30
31        // Change the head position based on the direction.
32        switch (direction) {
33            case "U":
34                newRow--;
35                break;
36            case "D":
37                newRow++;
38                break;
39            case "L":
40                newCol--;
41                break;
42            case "R":
43                newCol++;
44                break;
45        }
46
47        // Check if the new head position is out of bounds.
48        if (newRow < 0 || newRow >= height || newCol < 0 || newCol >= width) {
49            return -1;
50        }
51
52        // Check if the snake eats food.
53        if (foodIndex < food.length && newRow == food[foodIndex][0] && newCol == food[foodIndex][1]) {
54            score++;
55            foodIndex++;
56        } else { 
57            // If not eating, move the tail.
58            int tail = snakeBody.pollLast();
59            visited.remove(tail);
60        }
61
62        int newHead = flattenPosition(newRow, newCol);
63      
64        // Check if the snake bites itself.
65        if (visited.contains(newHead)) {
66            return -1;
67        }
68
69        // Add the new head to the snake body and mark it as visited.
70        snakeBody.offerFirst(newHead);
71        visited.add(newHead);
72
73        return score;
74    }
75
76    // Converts 2D grid coordinates to a single integer.
77    private int flattenPosition(int i, int j) {
78        return i * width + j;
79    }
80}
81

1#include <string>
2#include <vector>
3#include <deque>
4#include <unordered_set>
5using namespace std;
6
7class SnakeGame {
8public:
9    // Constructor to initialize the game with width, height, and food positions
10    SnakeGame(int width, int height, vector<vector<int>>& food) {
11        m_width = width;
12        m_height = height;
13        m_food = food;
14        m_score = 0;
15        m_foodIndex = 0;
16        snake.push_front(encode(0, 0)); // Start with snake head at top-left corner
17        snake_positions.insert(0); // Mark the position as occupied
18    }
19
20    // Method to move the snake in the given direction and return the score
21    int move(string direction) {
22        int headCode = snake.front();
23        int row = headCode / m_width, col = headCode % m_width;
24        if (direction == "U") row--;
25        if (direction == "D") row++;
26        if (direction == "L") col--;
27        if (direction == "R") col++;
28      
29        // Check if the next position is out of bounds
30        if (row < 0 || row >= m_height || col < 0 || col >= m_width) {
31            return -1;
32        }
33      
34        // Check if the next position is food
35        if (m_foodIndex < m_food.size() && row == m_food[m_foodIndex][0] && col == m_food[m_foodIndex][1]) {
36            m_score++;
37            m_foodIndex++;
38        } else {
39            // Remove the tail position since we are moving forward
40            int tailCode = snake.back();
41            snake.pop_back();
42            snake_positions.erase(tailCode);
43        }
44      
45        int newHeadCode = encode(row, col);
46      
47        // Check for snake collision with itself
48        if (snake_positions.count(newHeadCode)) {
49            return -1;
50        }
51        // Add the new head to the snake deque and set of occupied positions
52        snake.push_front(newHeadCode);
53        snake_positions.insert(newHeadCode);
54      
55        return m_score;
56    }
57
58private:
59    int m_width;
60    int m_height;
61    vector<vector<int>> m_food;
62    int m_score;
63    int m_foodIndex;
64    deque<int> snake; // Stores the encoded positions of the snake parts
65    unordered_set<int> snake_positions; // Tracks occupied positions by the snake
66
67    // Helper function to encode 2D positions into a single integer
68    int encode(int row, int col) {
69        return row * m_width + col;
70    }
71};
72

1let gridHeight: number;
2let gridWidth: number;
3let foodCoordinates: number[][];
4let currentScore: number;
5let foodIndex: number;
6let snake: number[];
7let visited: Set<number>;
8
9function initializeGame(width: number, height: number, food: number[][]): void {
10    gridHeight = height;
11    gridWidth = width;
12    foodCoordinates = food;
13    currentScore = 0;
14    foodIndex = 0;
15    snake = [0]; // Snake starts in the top-left corner as per the initial 0 index in the queue.
16    visited = new Set([0]); // Set to keep track of all visited cells by the snake.
17}
18
19function moveSnake(direction: string): number {
20    let headPosition = snake[0];
21    let currentRow = Math.floor(headPosition / gridWidth);
22    let currentColumn = headPosition % gridWidth;
23    let nextRow = currentRow;
24    let nextColumn = currentColumn;
25
26    switch (direction) {
27        case 'U':
28            nextRow--;
29            break;
30        case 'D':
31            nextRow++;
32            break;
33        case 'L':
34            nextColumn--;
35            break;
36        case 'R':
37            nextColumn++;
38            break;
39    }
40
41    // Check if the next position is out of the grid bounds.
42    if (nextRow < 0 || nextRow >= gridHeight || nextColumn < 0 || nextColumn >= gridWidth) {
43        return -1; // Game over.
44    }
45
46    let nextPosition = nextRow * gridWidth + nextColumn;
47
48    // Check if the next position contains food.
49    if (foodIndex < foodCoordinates.length &&
50        nextRow === foodCoordinates[foodIndex][0] &&
51        nextColumn === foodCoordinates[foodIndex][1]) {
52        currentScore++; // Increase score as the snake has eaten food.
53        foodIndex++; // Move to the next food item.
54    } else {
55        // If no food is found, pop the tail of the snake.
56        let tailPosition = snake.pop()!;
57        visited.delete(tailPosition); // Remove the tail from visited cells.
58    }
59
60    // Check if the snake has collided with itself.
61    if (visited.has(nextPosition)) {
62        return -1; // Game over.
63    }
64
65    // Add the new head to the snake.
66    snake.unshift(nextPosition);
67    visited.add(nextPosition); // Mark the new head as visited.
68
69    return currentScore; // Return the current score.
70}
71
72// Example of usage:
73initializeGame(3, 2, [[1, 2], [0, 1]]);
74const gameResult1 = moveSnake('R'); // Move right.
75const gameResult2 = moveSnake('D'); // Move down.
76

Time and Space Complexity

Time Complexity

The time complexity for the move operation of the SnakeGame class is generally O(1) for every call. The primary operations consist of updating the head position, checking for collisions, eating food, and updating the snake body.

Updating Position & Checking Collisions: All these operations involve constant time arithmetic operations and checks, as they only depend on the current direction and the new potential head position.
Eating Food: This also involves a constant-time comparison to check if the new head position corresponds to the next item in the food list.
Updating Snake Body: In the case where the snake doesn't eat food, removing the tail (self.q.pop()) and checking for body collisions ((x, y) in self.vis) are both O(1) operations due to the double-ended queue deque and hash set self.vis.

Space Complexity

The space complexity of the SnakeGame is O(N + M) where N is the length of the snake and M is the total number of food items. This is because:

Snake Representation (self.q and self.vis): The snake is represented by a dequeue (self.q) and a set (self.vis). In the worst case, the snake can grow to fill the entire board, leading to a space complexity of O(N) where N is the number of cells on the board (maximum length of the snake).
Food List (self.food): The food list is stored in the self.food attribute and takes O(M) space, where M is the number of food items.

Therefore, the overall space complexity is determined by the space needed to store the snake and the food.

Learn more about how to find time and space complexity quickly using problem constraints.

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

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know