Problem

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0,0) with length = 1 unit.

You are given a list of food’s positions in row-column order. When a snake eats the food, its length and the game’s score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

When a food does appear on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

Examples

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Given width = 3, height = 2, and food = [[1,2],[0,1]].

Snake snake = new Snake(width, height, food);

Initially the snake appears at position (0,0) and the food at (1,2).

|S| | |
| | |F|

snake.move("R"); -> Returns 0

| |S| |
| | |F|

snake.move("D"); -> Returns 0

| | | |
| |S|F|

snake.move("R"); -> Returns 1 (Snake eats the first food and right after that, the second food appears at (0,1) )

| |F| |
| |S|S|

snake.move("U"); -> Returns 1

| |F|S|
| | |S|

snake.move("L"); -> Returns 2 (Snake eats the second food)

| |S|S|
| | |S|

snake.move("U"); -> Returns -1 (Game over because snake collides with border)

Solution

Method 1 – Simulation with Queue and Set

Intuition

We simulate the snake’s movement using a queue to represent its body and a set for fast collision checks. The snake’s head moves in the given direction, and we check for collisions with the wall or itself. When the snake eats food, it grows; otherwise, its tail moves forward.

Approach

  1. Use a queue to store the positions of the snake’s body, with the head at the end.
  2. Use a set to quickly check if the snake collides with itself.
  3. On each move:
    • Calculate the new head position based on the direction.
    • Check if the new head is out of bounds or collides with the body (excluding the tail, which will move).
    • If the new head is at the food position, increase the score and grow the snake (do not remove the tail).
    • Otherwise, move the snake forward by removing the tail and adding the new head.
  4. Return the current score, or -1 if the game is over.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    int w, h, score, foodIdx;
    vector<vector<int>> food;
    deque<pair<int, int>> snake;
    unordered_set<int> body;
    int encode(int x, int y) { return x * w + y; }
public:
    Solution(int width, int height, vector<vector<int>>& foodList)
        : w(width), h(height), score(0), foodIdx(0), food(foodList) {
        snake.push_back({0, 0});
        body.insert(0);
    }
    int move(string direction) {
        int dx = 0, dy = 0;
        if (direction == "U") dx = -1;
        else if (direction == "D") dx = 1;
        else if (direction == "L") dy = -1;
        else if (direction == "R") dy = 1;
        int nx = snake.back().first + dx, ny = snake.back().second + dy;
        if (nx < 0 || nx >= h || ny < 0 || ny >= w) return -1;
        int tail = encode(snake.front().first, snake.front().second);
        body.erase(tail);
        if (body.count(encode(nx, ny))) return -1;
        snake.push_back({nx, ny});
        body.insert(encode(nx, ny));
        if (foodIdx < food.size() && nx == food[foodIdx][0] && ny == food[foodIdx][1]) {
            ++score;
            ++foodIdx;
            body.insert(tail);
        } else {
            snake.pop_front();
        }
        return score;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

type SnakeGame struct {
    w, h, score, foodIdx int
    food [][]int
    snake [][]int
    body map[int]bool
}
func Constructor(width int, height int, food [][]int) SnakeGame {
    return SnakeGame{w: width, h: height, food: food, snake: [][]int{{0,0}}, body: map[int]bool{0: true}}
}
func (g *SnakeGame) encode(x, y int) int { return x*g.w + y }
func (g *SnakeGame) Move(direction string) int {
    dx, dy := 0, 0
    switch direction {
    case "U": dx = -1
    case "D": dx = 1
    case "L": dy = -1
    case "R": dy = 1
    }
    head := g.snake[len(g.snake)-1]
    nx, ny := head[0]+dx, head[1]+dy
    if nx < 0 || nx >= g.h || ny < 0 || ny >= g.w { return -1 }
    tail := g.encode(g.snake[0][0], g.snake[0][1])
    g.body[tail] = false
    if g.body[g.encode(nx, ny)] { return -1 }
    g.snake = append(g.snake, []int{nx, ny})
    g.body[g.encode(nx, ny)] = true
    if g.foodIdx < len(g.food) && nx == g.food[g.foodIdx][0] && ny == g.food[g.foodIdx][1] {
        g.score++
        g.foodIdx++
        g.body[tail] = true
    } else {
        g.snake = g.snake[1:]
    }
    return g.score
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    int w, h, score = 0, foodIdx = 0;
    int[][] food;
    Deque<int[]> snake = new LinkedList<>();
    Set<Integer> body = new HashSet<>();
    int encode(int x, int y) { return x * w + y; }
    public Solution(int width, int height, int[][] food) {
        this.w = width; this.h = height; this.food = food;
        snake.add(new int[]{0, 0});
        body.add(0);
    }
    public int move(String direction) {
        int dx = 0, dy = 0;
        if (direction.equals("U")) dx = -1;
        else if (direction.equals("D")) dx = 1;
        else if (direction.equals("L")) dy = -1;
        else if (direction.equals("R")) dy = 1;
        int[] head = snake.peekLast();
        int nx = head[0] + dx, ny = head[1] + dy;
        if (nx < 0 || nx >= h || ny < 0 || ny >= w) return -1;
        int tail = encode(snake.peekFirst()[0], snake.peekFirst()[1]);
        body.remove(tail);
        if (body.contains(encode(nx, ny))) return -1;
        snake.addLast(new int[]{nx, ny});
        body.add(encode(nx, ny));
        if (foodIdx < food.length && nx == food[foodIdx][0] && ny == food[foodIdx][1]) {
            score++;
            foodIdx++;
            body.add(tail);
        } else {
            snake.pollFirst();
        }
        return score;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution(width: Int, height: Int, val food: Array<IntArray>) {
    val w = width
    val h = height
    var score = 0
    var foodIdx = 0
    val snake = ArrayDeque<Pair<Int, Int>>().apply { add(0 to 0) }
    val body = mutableSetOf(0)
    fun encode(x: Int, y: Int) = x * w + y
    fun move(direction: String): Int {
        val (dx, dy) = when (direction) {
            "U" -> -1 to 0
            "D" -> 1 to 0
            "L" -> 0 to -1
            else -> 0 to 1
        }
        val (hx, hy) = snake.last()
        val nx = hx + dx
        val ny = hy + dy
        if (nx !in 0 until h || ny !in 0 until w) return -1
        val tail = encode(snake.first().first, snake.first().second)
        body.remove(tail)
        if (body.contains(encode(nx, ny))) return -1
        snake.addLast(nx to ny)
        body.add(encode(nx, ny))
        if (foodIdx < food.size && nx == food[foodIdx][0] && ny == food[foodIdx][1]) {
            score++
            foodIdx++
            body.add(tail)
        } else {
            snake.removeFirst()
        }
        return score
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.w, self.h = width, height
        self.food = food
        self.score = 0
        self.food_idx = 0
        self.snake = [(0, 0)]
        self.body = set([(0, 0)])
    def move(self, direction: str) -> int:
        dx, dy = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}[direction]
        hx, hy = self.snake[-1]
        nx, ny = hx + dx, hy + dy
        if not (0 <= nx < self.h and 0 <= ny < self.w):
            return -1
        tail = self.snake[0]
        self.body.remove(tail)
        if (nx, ny) in self.body:
            return -1
        self.snake.append((nx, ny))
        self.body.add((nx, ny))
        if self.food_idx < len(self.food) and [nx, ny] == self.food[self.food_idx]:
            self.score += 1
            self.food_idx += 1
            self.body.add(tail)
        else:
            self.snake.pop(0)
        return self.score
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

use std::collections::{VecDeque, HashSet};
struct Solution {
    w: i32,
    h: i32,
    score: i32,
    food_idx: usize,
    food: Vec<Vec<i32>>,
    snake: VecDeque<(i32, i32)>,
    body: HashSet<i32>,
}
impl Solution {
    fn encode(&self, x: i32, y: i32) -> i32 { x * self.w + y }
    fn new(width: i32, height: i32, food: Vec<Vec<i32>>) -> Self {
        let mut snake = VecDeque::new();
        snake.push_back((0, 0));
        let mut body = HashSet::new();
        body.insert(0);
        Self { w: width, h: height, score: 0, food_idx: 0, food, snake, body }
    }
    fn move_(&mut self, direction: String) -> i32 {
        let (dx, dy) = match direction.as_str() {
            "U" => (-1, 0),
            "D" => (1, 0),
            "L" => (0, -1),
            _ => (0, 1),
        };
        let (hx, hy) = *self.snake.back().unwrap();
        let (nx, ny) = (hx + dx, hy + dy);
        if nx < 0 || nx >= self.h || ny < 0 || ny >= self.w { return -1; }
        let tail = self.encode(self.snake.front().unwrap().0, self.snake.front().unwrap().1);
        self.body.remove(&tail);
        if self.body.contains(&self.encode(nx, ny)) { return -1; }
        self.snake.push_back((nx, ny));
        self.body.insert(self.encode(nx, ny));
        if self.food_idx < self.food.len() && nx == self.food[self.food_idx][0] && ny == self.food[self.food_idx][1] {
            self.score += 1;
            self.food_idx += 1;
            self.body.insert(tail);
        } else {
            self.snake.pop_front();
        }
        self.score
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    w: number;
    h: number;
    score: number = 0;
    foodIdx: number = 0;
    food: number[][];
    snake: [number, number][];
    body: Set<number>;
    constructor(width: number, height: number, food: number[][]) {
        this.w = width;
        this.h = height;
        this.food = food;
        this.snake = [[0, 0]];
        this.body = new Set([0]);
    }
    encode(x: number, y: number): number { return x * this.w + y; }
    move(direction: string): number {
        let dx = 0, dy = 0;
        if (direction === "U") dx = -1;
        else if (direction === "D") dx = 1;
        else if (direction === "L") dy = -1;
        else if (direction === "R") dy = 1;
        const [hx, hy] = this.snake[this.snake.length - 1];
        const nx = hx + dx, ny = hy + dy;
        if (nx < 0 || nx >= this.h || ny < 0 || ny >= this.w) return -1;
        const tail = this.encode(this.snake[0][0], this.snake[0][1]);
        this.body.delete(tail);
        if (this.body.has(this.encode(nx, ny))) return -1;
        this.snake.push([nx, ny]);
        this.body.add(this.encode(nx, ny));
        if (this.foodIdx < this.food.length && nx === this.food[this.foodIdx][0] && ny === this.food[this.foodIdx][1]) {
            this.score++;
            this.foodIdx++;
            this.body.add(tail);
        } else {
            this.snake.shift();
        }
        return this.score;
    }
}

Complexity

  • ⏰ Time complexity: O(1) per move, since all operations (insert, remove, check) on the queue and set are constant time.
  • 🧺 Space complexity: O(N), where N is the maximum length of the snake (at most width × height), for storing the snake’s body and set.