Design Snake Game
Problem
Design a snake game on a grid of given width and height with a list of food positions; implement a move function that moves the snake in the given direction, returns the game's score after the move, or -1 if the game is over due to collision or boundary crossing.
- 1 ≤ width, height ≤ 10⁴
- 0 ≤ food.length ≤ 10⁴
- food[i].length == 2
- 0 ≤ food[i][0] < height
- 0 ≤ food[i][1] < width
- direction is one of 'U', 'D', 'L', 'R'
Example
width = 3, height = 2, food = [[1,2],[0,1]]; moves = ['R', 'D', 'R', 'U', 'L', 'U'][0, 0, 1, 1, 2, -1]Initially, the snake is at (0,0). Move 'R' moves it to (0,1), no food eaten, score 0. Move 'D' to (1,1), no food, score 0. Move 'R' to (1,2), eats first food, snake grows, score 1. Move 'U' to (0,2), no food, score 1. Move 'L' to (0,1), eats second food, snake grows, score 2. Move 'U' to (-1,1), out of bounds, game over, returns -1.
Approach
Straightforward Solution
A naive approach might store the snake's body as a list and check for collisions by scanning the list, resulting in O(n) collision checks per move, which is inefficient for long snakes.
Core Observation
The snake's position and body must be tracked precisely to detect collisions with itself and boundaries. The snake moves by adding a new head and removing the tail unless it eats food, in which case it grows by not removing the tail. Efficient membership checks for the snake's body are essential to detect self-collisions in O(1) time.
Path to Optimal
PreviewThe key insight is to use a deque to represent the snake's body for O(1) head and tail operations, and a hash set to track body positions for O(1) collision detection…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a deque to store the snake's body coordinates with the head at the front and a set for constant-time membership checks. On each move, compute the new head position, remove the tail from the set and deque, check for collisions, then add the new head…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(1) per move
Each move involves constant-time operations: deque pop and append, set add and remove, and simple arithmetic for position updates. Collision checks are O(1) due to the set.
Space
O(n)
The snake's body can grow up to the size of the grid or the number of food items, so the deque and set store up to O(n) positions, where n is the number of moves or food items.
Pattern Spotlight
Simulation (Stateful Grid Movement with Collision Detection)
When simulating a moving object with a dynamic body on a grid, maintain both an ordered structure for the body and a hash set for quick collision checks, carefully updating these in the correct order to avoid false positives when the tail moves forward.
Solution
| 1 | class SnakeGame: |
| 2 | def __init__(self, width: int, height: int, food: List[List[int]]): |
| 3 | self.width = width |
| 4 | self.height = height |
| 5 | self.food = food |
| 6 | self.food_index = 0 |
| 7 | self.snake = deque([(0, 0)]) |
| 8 | self.body = {(0, 0)} |
| 9 | self.score = 0 |
| 10 | self.dirs = { |
| 11 | "U": (-1, 0), |
| 12 | "D": (1, 0), |
| 13 | "L": (0, -1), |
| 14 | "R": (0, 1) |
| 15 | } |
| 16 | |
| 17 | def move(self, direction: str) -> int: |
| 18 | dr, dc = self.dirs[direction] |
| 19 | head_r, head_c = self.snake[0] |
| 20 | new_r, new_c = head_r + dr, head_c + dc |
| 21 | new_head = (new_r, new_c) |
| 22 | |
| 23 | if not (0 <= new_r < self.height and 0 <= new_c < self.width): |
| 24 | return -1 |
| 25 | |
| 26 | tail = self.snake.pop() |
| 27 | self.body.remove(tail) |
| 28 | |
| 29 | if new_head in self.body: |
| 30 | return -1 |
| 31 | |
| 32 | self.snake.appendleft(new_head) |
| 33 | self.body.add(new_head) |
| 34 | |
| 35 | if self.food_index < len(self.food) and new_head == tuple(self.food[self.food_index]): |
| 36 | self.food_index += 1 |
| 37 | self.score += 1 |
| 38 | self.snake.append(tail) |
| 39 | self.body.add(tail) |
| 40 | |
| 41 | return self.score |
Step-by-Step Solution
Initialize Snake State and Movement Directions
| 3 | self.width = width |
| 4 | self.height = height |
| 5 | self.food = food |
| 6 | self.food_index = 0 |
| 7 | self.snake = deque([(0, 0)]) |
| 8 | self.body = {(0, 0)} |
| 9 | self.score = 0 |
| 10 | self.dirs = { |
| 11 | "U": (-1, 0), |
| 12 | "D": (1, 0), |
| 13 | "L": (0, -1), |
| 14 | "R": (0, 1) |
| 15 | } |
Objective
To set up the initial game state including grid dimensions, food list, snake body tracking, and movement direction mappings.
Key Insight
Representing the snake's body as both a deque and a set allows efficient updates and collision detection. The deque maintains the order of the snake's segments for head and tail operations, while the set enables O(1) membership checks. Predefining direction vectors simplifies move calculations and reduces errors.
Interview Quick-Check
Core Logic
Using a deque for the snake's body preserves order for head/tail operations, while a set tracks occupied positions for constant-time collision detection.
Common Pitfalls & Bugs
Failing to keep the set and deque in sync can cause incorrect collision detection or state corruption.
State & Boundaries
Initialize the snake at position (0, 0) with score zero and food index zero to track progress through the food list.
Compute New Head Position and Check Boundary Collision
To calculate the snake's next head position based on the input direction and verify it remains within grid boundaries.
Update Snake Body by Moving Tail and Detect Self-Collision
To simulate the snake moving forward by removing the tail, then check if the new head collides with the body.
Add New Head and Handle Food Consumption to Grow Snake
To add the new head position to the snake's body and grow the snake if food is eaten at the new head location.
Return Current Score or Game Over Indicator
To return the current score after a successful move or -1 if the game ended due to collision or boundary crossing.
4 more steps with full analysis available on Pro.
Line Analysis
This solution has 10 Critical lines interviewers watch for.
return -1Return -1 to indicate game over due to boundary collision.
Returning -1 signals to the caller that the game has ended because the snake moved out of bounds.
if new_head in self.body:Check if the new head position collides with the snake's body.
Detecting self-collision is critical to end the game when the snake bites itself.
return -1Return -1 to indicate game over due to self-collision.
Returning -1 signals the game has ended because the snake collided with itself.
Full line-by-line criticality + rationale for all 32 lines available on Pro.
Test Your Understanding
Why is the tail removed from the body set before checking for collisions with the new head position?
See the answer with Pro.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Design Snake Game from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Design Snake Game drill