Design Snake Game
Design Snake Game is a medium design data structures problem solved with the queue / circular buffer pattern.
The best approach, optimal (deque + hash set of occupied cells), runs in O(1) per move time and O(L + F) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list body, scan for collisions) up.
Problem
Design the classic Snake game on a board with height rows and width columns. The snake starts as a single cell at the top-left corner (0, 0). You are also given food, a list of cells [row, col]; the pieces appear one at a time in that order, and the next one shows up only after the current one has been eaten.
Implement SnakeGame:
SnakeGame(int width, int height, int[][] food)sets up the board and the food list.int move(String direction)moves the head one cell"U"(up),"D"(down),"L"(left) or"R"(right) and returns the score, the number of food pieces eaten so far. When the head lands on the current food, the snake grows by one cell (its tail stays where it was) and the score goes up by one.
The game ends when the head leaves the board or runs into the snake’s own body. The tail moves out of its cell in the same step, so stepping into the cell the tail is just leaving is fine. When a move ends the game, return -1; every later call to move also returns -1.
Examples
Example 1
- Input
SnakeGame(3, 2, [[1, 2], [0, 1]]), move("R"), move("D"), move("R"), move("U"), move("L"), move("U")- Output
0, 0, 1, 1, 2, -1- Why
- The snake reaches the first food at (1,2) on the third move and the second at (0,1) on the fifth; the last move leaves the board through the top.
Example 2
- Input
SnakeGame(2, 2, [[0, 1], [1, 1], [1, 0]]), move("R"), move("D"), move("L"), move("U"), move("R"), move("L"), move("D")- Output
1, 2, 3, 3, 3, -1, -1- Why
- After three meals the snake fills the board. Moving into the cell the tail is just leaving is allowed, but turning back onto (0,0) hits the body; after that every move returns -1.
Constraints
1 <= width, height <= 10^41 <= food.length <= 50food[i] = [row, col]with0 <= row < heightand0 <= col < widthdirectionis one of"U","D","L","R".- At most
10^4calls tomove. - A food item never appears on a cell occupied by the snake, and it is never at
(0, 0).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (list body, scan for collisions) | O(L) per move | O(L + F) |
| Optimal (deque + hash set of occupied cells) | O(1) per move | O(L + F) |
1Brute force (list body, scan for collisions)
O(L) per moveThe collision check scans all L cells of the snake.O(L + F)The body list holds L cells and the food list F items.Keep the body as a list of cells with the head at the front. For each move compute the new head, check the walls, decide whether it eats the next food, remove the tail if it does not, then scan the whole body to see whether the new head lands on it.
- If the game is already over, return -1.
- Compute the new head from the direction; if it is off the board, end the game and return -1.
eatis true when the next unused food sits on the new head. If not eating, remove the last cell of the body.- Scan the body; if any cell equals the new head, end the game and return -1.
- Add the new head at the front. If eating, increase the score and move to the next food. Return the score.
class SnakeGame {
private final int width, height;
private final int[][] food;
private final LinkedList<int[]> body = new LinkedList<>();
private int foodIdx = 0, score = 0;
private boolean over = false;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
body.addFirst(new int[] { 0, 0 });
}
public int move(String direction) {
if (over) return -1;
int r = body.getFirst()[0], c = body.getFirst()[1];
switch (direction) {
case "U": r--; break;
case "D": r++; break;
case "L": c--; break;
default: c++;
}
if (r < 0 || r >= height || c < 0 || c >= width) {
over = true;
return -1;
}
boolean eat = foodIdx < food.length && food[foodIdx][0] == r && food[foodIdx][1] == c;
if (!eat) body.removeLast();
for (int[] cell : body) {
if (cell[0] == r && cell[1] == c) {
over = true;
return -1;
}
}
body.addFirst(new int[] { r, c });
if (eat) {
score++;
foodIdx++;
}
return score;
}
}class SnakeGame:
def __init__(self, width: int, height: int, food: List[List[int]]):
self.width = width
self.height = height
self.food = food
self.body = [(0, 0)]
self.food_idx = 0
self.score = 0
self.over = False
def move(self, direction: str) -> int:
if self.over:
return -1
r, c = self.body[0]
if direction == "U":
r -= 1
elif direction == "D":
r += 1
elif direction == "L":
c -= 1
else:
c += 1
if r < 0 or r >= self.height or c < 0 or c >= self.width:
self.over = True
return -1
eat = self.food_idx < len(self.food) and self.food[self.food_idx][0] == r and self.food[self.food_idx][1] == c
if not eat:
self.body.pop()
for cell in self.body:
if cell == (r, c):
self.over = True
return -1
self.body.insert(0, (r, c))
if eat:
self.score += 1
self.food_idx += 1
return self.scoreclass SnakeGame {
int width, height;
vector<vector<int>> food;
deque<pair<int, int>> body;
int foodIdx = 0, score = 0;
bool over = false;
public:
SnakeGame(int width, int height, vector<vector<int>>& food) : width(width), height(height), food(food) {
body.push_front({0, 0});
}
int move(string direction) {
if (over) return -1;
int r = body.front().first, c = body.front().second;
if (direction == "U") r--;
else if (direction == "D") r++;
else if (direction == "L") c--;
else c++;
if (r < 0 || r >= height || c < 0 || c >= width) {
over = true;
return -1;
}
bool eat = foodIdx < (int) food.size() && food[foodIdx][0] == r && food[foodIdx][1] == c;
if (!eat) body.pop_back();
for (auto& cell : body) {
if (cell.first == r && cell.second == c) {
over = true;
return -1;
}
}
body.push_front({r, c});
if (eat) {
score++;
foodIdx++;
}
return score;
}
};class SnakeGame {
constructor(width, height, food) {
this.width = width;
this.height = height;
this.food = food;
this.body = [[0, 0]];
this.foodIdx = 0;
this.score = 0;
this.over = false;
}
move(direction) {
if (this.over) return -1;
let [r, c] = this.body[0];
if (direction === "U") r--;
else if (direction === "D") r++;
else if (direction === "L") c--;
else c++;
if (r < 0 || r >= this.height || c < 0 || c >= this.width) {
this.over = true;
return -1;
}
const f = this.food[this.foodIdx];
const eat = this.foodIdx < this.food.length && f[0] === r && f[1] === c;
if (!eat) this.body.pop();
for (const [br, bc] of this.body) {
if (br === r && bc === c) {
this.over = true;
return -1;
}
}
this.body.unshift([r, c]);
if (eat) {
this.score++;
this.foodIdx++;
}
return this.score;
}
}2Optimal (deque + hash set of occupied cells)
O(1) per moveEach move does a constant number of deque and hash-set operations.O(L + F)The deque and the set each hold the L cells of the snake; the food list holds F items.Keep the same move logic, but store the body in a deque of encoded cells (row * width + col) and mirror it in a hash set. Removing the tail and adding the head touch both structures in O(1), and the collision test becomes a single set lookup.
- Start with the deque and the set both holding cell 0.
- On a move, compute the new head and check the walls.
- If it does not eat, pop the tail from the deque and remove it from the set.
- If the set already contains the new head, the snake bit itself: end the game.
- Push the head onto the deque and into the set; on eating, bump the score and the food index.
class SnakeGame {
private final int width, height;
private final int[][] food;
private final Deque<Integer> body = new ArrayDeque<>();
private final Set<Integer> occupied = new HashSet<>();
private int foodIdx = 0, score = 0;
private boolean over = false;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
body.addFirst(0);
occupied.add(0);
}
public int move(String direction) {
if (over) return -1;
int head = body.peekFirst();
int r = head / width, c = head % width;
switch (direction) {
case "U": r--; break;
case "D": r++; break;
case "L": c--; break;
default: c++;
}
if (r < 0 || r >= height || c < 0 || c >= width) {
over = true;
return -1;
}
boolean eat = foodIdx < food.length && food[foodIdx][0] == r && food[foodIdx][1] == c;
if (!eat) occupied.remove(body.pollLast());
int cell = r * width + c;
if (occupied.contains(cell)) {
over = true;
return -1;
}
body.addFirst(cell);
occupied.add(cell);
if (eat) {
score++;
foodIdx++;
}
return score;
}
}class SnakeGame:
def __init__(self, width: int, height: int, food: List[List[int]]):
self.width = width
self.height = height
self.food = food
self.body = deque([0])
self.occupied = {0}
self.food_idx = 0
self.score = 0
self.over = False
def move(self, direction: str) -> int:
if self.over:
return -1
r, c = divmod(self.body[0], self.width)
if direction == "U":
r -= 1
elif direction == "D":
r += 1
elif direction == "L":
c -= 1
else:
c += 1
if r < 0 or r >= self.height or c < 0 or c >= self.width:
self.over = True
return -1
eat = self.food_idx < len(self.food) and self.food[self.food_idx][0] == r and self.food[self.food_idx][1] == c
if not eat:
self.occupied.discard(self.body.pop())
cell = r * self.width + c
if cell in self.occupied:
self.over = True
return -1
self.body.appendleft(cell)
self.occupied.add(cell)
if eat:
self.score += 1
self.food_idx += 1
return self.scoreclass SnakeGame {
int width, height;
vector<vector<int>> food;
deque<long long> body;
unordered_set<long long> occupied;
int foodIdx = 0, score = 0;
bool over = false;
public:
SnakeGame(int width, int height, vector<vector<int>>& food) : width(width), height(height), food(food) {
body.push_front(0);
occupied.insert(0);
}
int move(string direction) {
if (over) return -1;
long long head = body.front();
int r = head / width, c = head % width;
if (direction == "U") r--;
else if (direction == "D") r++;
else if (direction == "L") c--;
else c++;
if (r < 0 || r >= height || c < 0 || c >= width) {
over = true;
return -1;
}
bool eat = foodIdx < (int) food.size() && food[foodIdx][0] == r && food[foodIdx][1] == c;
if (!eat) {
occupied.erase(body.back());
body.pop_back();
}
long long cell = (long long) r * width + c;
if (occupied.count(cell)) {
over = true;
return -1;
}
body.push_front(cell);
occupied.insert(cell);
if (eat) {
score++;
foodIdx++;
}
return score;
}
};class SnakeGame {
constructor(width, height, food) {
this.width = width;
this.height = height;
this.food = food;
this.body = [0];
this.headIdx = 0;
this.occupied = new Set([0]);
this.foodIdx = 0;
this.score = 0;
this.over = false;
}
move(direction) {
if (this.over) return -1;
const head = this.body[this.body.length - 1];
let r = Math.floor(head / this.width), c = head % this.width;
if (direction === "U") r--;
else if (direction === "D") r++;
else if (direction === "L") c--;
else c++;
if (r < 0 || r >= this.height || c < 0 || c >= this.width) {
this.over = true;
return -1;
}
const f = this.food[this.foodIdx];
const eat = this.foodIdx < this.food.length && f[0] === r && f[1] === c;
if (!eat) {
this.occupied.delete(this.body[this.headIdx]);
this.headIdx++;
}
const cell = r * this.width + c;
if (this.occupied.has(cell)) {
this.over = true;
return -1;
}
this.body.push(cell);
this.occupied.add(cell);
if (eat) {
this.score++;
this.foodIdx++;
}
return this.score;
}
}Edge cases to test
- Moving into the cell the tail is leaving on the same move is allowed (unless the snake is eating, because then the tail stays)
- Leaving the board on any side ends the game
- After the game is over, every further call returns -1
- All food eaten: the snake keeps moving without growing
- A one-cell-wide board: the snake can only move along a single line
Hints
Hint 1
Store the snake as a sequence of cells from tail to head. A normal move adds a new head and drops the tail; eating adds a head and keeps the tail.
Hint 2
Order matters: drop the tail before checking whether the new head hits the body, otherwise following your own tail looks like a crash.
Hint 3
A deque gives O(1) head and tail updates; a hash set of occupied cells next to it gives O(1) collision checks.
FAQ
What is the best time complexity for Design Snake Game?
Optimal (deque + hash set of occupied cells) runs in O(1) per move time and O(L + F) extra space. Each move does a constant number of deque and hash-set operations.
Which pattern does Design Snake Game use?
It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Hit Counter, Design Circular Queue, First Unique Number.
Is there a brute force solution for Design Snake Game?
Yes. Brute force (list body, scan for collisions) takes O(L) per move time and O(L + F) space. Keep the body as a list of cells with the head at the front.
Which edge cases should I test for Design Snake Game?
Moving into the cell the tail is leaving on the same move is allowed (unless the snake is eating, because then the tail stays); Leaving the board on any side ends the game; After the game is over, every further call returns -1; All food eaten: the snake keeps moving without growing; A one-cell-wide board: the snake can only move along a single line.