Editorial
Core insight
Design Snake Game · Design Patterns
Core Insight for Design Snake Game
The core insight for solving LeetCode 353 efficiently is to decouple the snake's body from the full grid dimensions. Instead of tracking the state of every cell on the board, we only track the cells currently occupied by the snake.
The snake's movement follows a First-In-First-Out (FIFO) behavior, but with a twist. When the snake moves:
- A new head is added to the front.
- The old tail is removed from the back (unless food is eaten).
This behavior perfectly matches a Deque (Double-Ended Queue). The Deque maintains the order of the body segments, allowing us to identify the current tail and head in time.
However, a Deque alone is insufficient for collision detection. To check if the new head collides with the body, we would have to iterate through the Deque, taking time. To optimize this to , we use a secondary data structure: a Hash Set. The Set stores the coordinates of all body parts strictly for fast lookup.
Visual Description:
Imagine the snake as a sequence of nodes. When the move function is called, we calculate a candidate coordinate for the new head. Before finalizing the move, we must decide what happens to the tail. If the candidate coordinate is not food, the tail node is popped from the back of the Deque and removed from the Hash Set. Crucially, this removal happens before we check for self-collision with the new head. This order of operations allows the snake to move into the space its tail just vacated (chasing its tail) without triggering a "game over."
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 353: Design Snake Game Solution & Explanation
Problem Overview
TL;DR: The optimal solution utilizes a Double-Ended Queue (Deque) to store the snake's body coordinates for ordered movement and a Hash Set for O(1) collision detection.
The Design Snake Game problem asks us to simulate the classic Snake game on a grid of size width x height. We start at position (0,0) with an initial length of 1. We are given a specific sequence of food positions. The core functionality involves implementing a move method that updates the snake's position based on a direction ('U', 'D', 'L', 'R'). The game ends if the snake hits a wall or collides with its own body. If the snake eats food, it grows; otherwise, it maintains its length by moving its tail forward.
This is a popular interview question that tests object-oriented design skills and the ability to manage state efficiently using appropriate data structures.
Brute Force Approach for Design Snake Game
A naive approach to solving LeetCode 353 is to represent the entire game board as a 2D array (grid).
In this approach, we might maintain a grid[height][width] where each cell stores a value indicating whether it is empty, contains food, or contains a part of the snake's body. When the snake moves, we calculate the new head position, check the value in the grid, and update the grid cells accordingly. To simulate movement, we would also need to store the body coordinates in a list to know which cell corresponds to the tail that needs clearing.
1# Pseudo-code for Naive Approach
2class SnakeGame:
3 def __init__(self, width, height, food):
4 self.grid = [[0] * width for _ in range(height)] # 0: Empty, 1: Body
5 self.snake_body = [(0, 0)]
6 self.grid[0][0] = 1
7 # ... store food ...
8
9 def move(self, direction):
10 # Calculate new_head
11 # Check bounds
12 # Iterate through snake_body to check collision (O(N))
13 # Update grid and listWhy this fails:
- Space Complexity: The constraints state that
widthandheightcan be up to . A 2D array of size requires entries. This consumes excessive memory (potentially hundreds of megabytes), likely causing a Memory Limit Exceeded error or extremely slow initialization. - Inefficiency: We only care about the cells occupied by the snake and the food. Since the snake's length is relatively small compared to the grid size, allocating space for the entire grid is a waste of resources.
Algorithm Strategy: Design Patterns
We will implement a class that maintains the game state using a Deque for the snake's body and a Hash Set for occupied positions. We will also track the score and the index of the next available food item.
-
State Management:
snake: A Deque storing integer pairs (or a single hashed integer) representing(row, col)of the body segments. The front is the head; the back is the tail.occupied: A Hash Set storing the same values as the Deque for existence checks.food: The list of food coordinates provided in the input.score: An integer tracking the number of food items eaten (also serves as the index for thefoodarray).width,height: Grid boundaries.
-
Coordinate Hashing: To simplify storage in the Set (especially in languages like C++ or Java where pairs/arrays might need custom hashers), we can flatten the 2D coordinate
(r, c)into a 1D integer using the formula:hash = r * width + c. This guarantees a unique ID for every cell since0 <= c < width. -
Movement Logic:
- Compute the new head position based on the current head and the input direction.
- Check if the new head is out of grid bounds. If so, return -1.
- Check if the new head is at the current food position.
- If Food: The snake grows. The new head is added, but the tail is not removed. Score increments.
- If No Food: The snake moves. The tail is removed from the Deque and the Set. Then, we add the new head.
- Check if the new head collides with the body (exists in the
occupiedSet).- Note: By removing the tail before this check (in the non-food case), we correctly handle the case where the head moves into the cell just vacated by the tail.
- Update the Deque and Set with the new head.
Execution Flow
Let's trace a move operation where the snake is at [(0,1), (0,0)] (Head at (0,1)), moving Right (R), and there is no food.
- Input:
move('R'). - Current Head:
(0,1). - New Head Calculation:
(0, 1+1)->(0,2). - Boundary Check: Is
0 <= 0 < heightand0 <= 2 < width? Yes. Proceed. - Food Check: Is
(0,2)the next food item? No. - Tail Handling:
- Since we are not eating, we must remove the tail to maintain length.
- Pop
(0,0)from the Deque back. - Remove
(0,0)from theoccupiedSet. - Current Body in Set:
{(0,1)}.
- Self-Collision Check:
- Does
occupiedcontain(0,2)? No. - Proceed.
- Does
- Update State:
- Push
(0,2)to Deque front. - Add
(0,2)tooccupiedSet.
- Push
- Return: Score (e.g., 0).
Proof of Correctness
The algorithm is correct because it faithfully simulates the rules of Snake while enforcing invariants efficiently:
- Connectivity: The Deque structure ensures that body segments are always stored in the order of movement.
- Collision Accuracy: The Hash Set provides immediate feedback on whether a coordinate is occupied.
- Tail-Chasing Edge Case: By removing the tail from the
occupiedset before checking the new head's validity (in non-eating moves), we allow the valid move where the head enters the cell the tail just left. If we checked first, this valid move would be flagged as a collision. - Bounds: Explicit checks against
widthandheightensure the snake stays within the grid.
Pattern Reuse Notes
The Design (General/Specific) pattern, specifically using a Deque combined with a Hash Map/Set for O(1) access and ordered tracking, is used in several high-frequency interview problems:
- LeetCode 146: LRU Cache - Uses a Doubly Linked List (conceptually similar to Deque) for order and a Map for access.
- LeetCode 155: Min Stack - Uses auxiliary data structures to maintain state properties (minimum value) alongside the main data.
- LeetCode 225: Implement Stack using Queues - Manipulating data order using restricted standard data structures.
- LeetCode 232: Implement Queue using Stacks - Similar to above, focusing on state inversion.
Mastering the interaction between ordered lists (Queue/Deque) and fast lookups (Hash Table) is crucial for these Design problems.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 353
1#include <deque>
2#include <vector>
3#include <string>
4#include <unordered_set>
5
6using namespace std;
7
8class SnakeGame {
9private:
10 int width;
11 int height;
12 int score;
13 vector<vector<int>> food;
14 int foodIndex;
15
16 // Stores body positions (r * width + c) for O(1) lookup
17 unordered_set<int> occupied;
18 // Stores body positions (r * width + c) for order
19 deque<int> snake;
20
21public:
22 SnakeGame(int width, int height, vector<vector<int>>& food) {
23 this->width = width;
24 this->height = height;
25 this->food = food;
26 this->score = 0;
27 this->foodIndex = 0;
28
29 // Initialize snake at (0,0)
30 int start = 0; // 0 * width + 0
31 snake.push_back(start);
32 occupied.insert(start);
33 }
34
35 int move(string direction) {
36 // Get current head coordinates
37 int headVal = snake.front();
38 int r = headVal / width;
39 int c = headVal % width;
40
41 // Calculate new head
42 if (direction == "U") r--;
43 else if (direction == "D") r++;
44 else if (direction == "L") c--;
45 else if (direction == "R") c++;
46
47 // 1. Check Bounds
48 if (r < 0 || r >= height || c < 0 || c >= width) {
49 return -1;
50 }
51
52 int newHeadVal = r * width + c;
53
54 // 2. Handle Food and Tail
55 // Check if the new position is the current food
56 // Be careful: foodIndex must be within bounds
57 bool isFood = false;
58 if (foodIndex < food.size() && food[foodIndex][0] == r && food[foodIndex][1] == c) {
59 isFood = true;
60 }
61
62 if (isFood) {
63 score++;
64 foodIndex++;
65 // If eating, tail stays. We do NOT remove from occupied/deque.
66 } else {
67 // If not eating, tail moves. Remove tail BEFORE collision check.
68 int tailVal = snake.back();
69 snake.pop_back();
70 occupied.erase(tailVal);
71 }
72
73 // 3. Check Self-Collision
74 if (occupied.count(newHeadVal)) {
75 return -1;
76 }
77
78 // 4. Finalize Move
79 snake.push_front(newHeadVal);
80 occupied.insert(newHeadVal);
81
82 return score;
83 }
84};Java Solution for LeetCode 353
1import java.util.*;
2
3class SnakeGame {
4 private int width;
5 private int height;
6 private int score;
7 private int[][] food;
8 private int foodIndex;
9
10 // Store body as 1D coordinates: r * width + c
11 private Deque<Integer> snake;
12 private Set<Integer> occupied;
13
14 public SnakeGame(int width, int height, int[][] food) {
15 this.width = width;
16 this.height = height;
17 this.food = food;
18 this.score = 0;
19 this.foodIndex = 0;
20
21 this.snake = new LinkedList<>();
22 this.occupied = new HashSet<>();
23
24 // Initialize at (0,0)
25 snake.offerFirst(0);
26 occupied.add(0);
27 }
28
29 public int move(String direction) {
30 int headVal = snake.peekFirst();
31 int r = headVal / width;
32 int c = headVal % width;
33
34 if (direction.equals("U")) r--;
35 else if (direction.equals("D")) r++;
36 else if (direction.equals("L")) c--;
37 else if (direction.equals("R")) c++;
38
39 // 1. Check Bounds
40 if (r < 0 || r >= height || c < 0 || c >= width) {
41 return -1;
42 }
43
44 int newHeadVal = r * width + c;
45
46 // 2. Handle Food and Tail
47 // Identify if we are eating food
48 boolean isFood = false;
49 if (foodIndex < food.length && food[foodIndex][0] == r && food[foodIndex][1] == c) {
50 isFood = true;
51 }
52
53 if (isFood) {
54 score++;
55 foodIndex++;
56 // Tail stays; do not pop.
57 } else {
58 // Tail moves; pop from back and remove from set
59 int tailVal = snake.pollLast();
60 occupied.remove(tailVal);
61 }
62
63 // 3. Check Self-Collision
64 // Note: If we didn't eat, tail is already removed, so chasing tail is safe.
65 if (occupied.contains(newHeadVal)) {
66 return -1;
67 }
68
69 // 4. Update State
70 snake.offerFirst(newHeadVal);
71 occupied.add(newHeadVal);
72
73 return score;
74 }
75}Python Solution for LeetCode 353
1from collections import deque
2
3class SnakeGame:
4
5 def __init__(self, width: int, height: int, food: list[list[int]]):
6 self.width = width
7 self.height = height
8 self.food = food
9 self.food_index = 0
10 self.score = 0
11
12 # Snake body as deque of (row, col)
13 # We assume (0,0) is initial position
14 self.snake = deque([(0, 0)])
15 # Set for O(1) collision lookup
16 self.occupied = {(0, 0)}
17
18 def move(self, direction: str) -> int:
19 # Current head
20 r, c = self.snake[0]
21
22 # Compute new head
23 if direction == 'U': r -= 1
24 elif direction == 'D': r += 1
25 elif direction == 'L': c -= 1
26 elif direction == 'R': c += 1
27
28 # 1. Check Bounds
29 if not (0 <= r < self.height and 0 <= c < self.width):
30 return -1
31
32 new_head = (r, c)
33
34 # 2. Check Food
35 # If current position matches next food item
36 if self.food_index < len(self.food) and \
37 self.food[self.food_index][0] == r and \
38 self.food[self.food_index][1] == c:
39 self.score += 1
40 self.food_index += 1
41 # Tail stays, so we do NOT pop from snake or remove from occupied
42 else:
43 # Normal move: remove tail
44 tail = self.snake.pop()
45 self.occupied.remove(tail)
46
47 # 3. Check Self-Collision
48 # If new_head is in occupied set, it's a collision
49 if new_head in self.occupied:
50 return -1
51
52 # 4. Finalize Move
53 self.snake.appendleft(new_head)
54 self.occupied.add(new_head)
55
56 return self.score