353. Design Snake Game 🔒
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:
-
SnakeGame(int width, int height, int[][] food)
: Constructor that initializes the game with the screen dimensions and food positions -
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).
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:
- Add a new head to the right of the current head
- 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:
- First, calculate where the new head would be
- Check if it's out of bounds (wall collision)
- Check if it's food - if yes, eat it (increment score and food index)
- If not food, remove the tail from both the deque and the set
- Check if the new head position collides with the body (now that tail is removed if needed)
- 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 0self.vis
: A set that stores all positions occupied by the snake for O(1) collision checkingself.food
: Array of food positionsself.idx
: Current food index to track which food item should appear nextself.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):
-
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)
-
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)
-
Check boundary collision:
if x < 0 or x >= self.m or y < 0 or y >= self.n: return -1 # Game over - hit wall
-
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())
-
Check self-collision:
if (x, y) in self.vis: return -1 # Game over - snake hit itself
-
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 EvaluatorExample 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
- Current head: (0,0), calculate new position: (0,1)
- Check bounds: 0≤0<3 and 0≤1<3 ✓
- Not food position, remove tail from (0,0)
- Check collision: (0,1) not in body ✓
- Add new head at (0,1)
[ ][S][ ] Score = 0 [ ][ ][F] [ ][ ][ ]
Move 2: move("D") - Move down
- Current head: (0,1), new position: (1,1)
- Check bounds: ✓
- Not food, remove tail
- No collision ✓
- Add new head at (1,1)
[ ][ ][ ] Score = 0 [ ][S][F] [ ][ ][ ]
Move 3: move("R") - Move right (eat food!)
- Current head: (1,1), new position: (1,2)
- Check bounds: ✓
- Food at (1,2)! Score increases, don't remove tail
- No collision ✓
- 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
- Current head: (1,2), new position: (2,2)
- Check bounds: ✓
- Not food, remove tail from (1,1)
- No collision ✓
- Add new head at (2,2)
[ ][ ][ ] Score = 1 [ ][ ][B] [F][ ][S] Snake: (2,2)→(1,2)
Move 5: move("L") - Move left
- Current head: (2,2), new position: (2,1)
- Check bounds: ✓
- Not food, remove tail from (1,2)
- No collision ✓
- Add new head at (2,1)
[ ][ ][ ] Score = 1 [ ][ ][ ] [F][S][B] Snake: (2,1)→(2,2)
Move 6: move("L") - Move left (eat food!)
- Current head: (2,1), new position: (2,0)
- Check bounds: ✓
- Food at (2,0)! Score increases, don't remove tail
- No collision ✓
- 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)
- Current head: (2,0), new position: (1,0)
- Check bounds: ✓
- Not food, remove tail from (2,2)
- No collision ✓
- 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)
- Current head: (1,0), new position: (0,0)
- Check bounds: ✓
- Not food, remove tail from (2,1)
- No collision ✓
- 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)
- Current head: (0,0), new position: (-1,0)
- Check bounds: -1 < 0 - Out of bounds!
- 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 bothO(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 bothappendleft
andpop
- Adding/removing from set:
O(1)
average case for both operations - Checking membership in set:
O(1)
average case
- Direction calculation:
Space Complexity:
O(W × H)
in the worst case, whereW
is the width andH
is the height of the game board.- The space is primarily used by:
self.q
(deque): Can grow up to sizeW × H
if the snake fills the entire boardself.vis
(set): Maintains the same positions as the deque, so also up toW × H
elementsself.food
:O(F)
whereF
is the number of food items, but this is typically much smaller thanW × H
- In practice, the space complexity is
O(min(S, W × H))
whereS
is the current length of the snake, since the snake's body occupiesS
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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!