Design Snake Game - Video Solutions
LeetCode 353. Design Snake Game
Design Snake Game - Video Solution
Watch 9 video solutions for Design Snake Game, a medium level problem involving Array, Hash Table, Design. This walkthrough by Happy Coding has 10,863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Design a Snake game that is played on a device with screen size height x width. 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 a length of 1 unit.
You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.
Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.
When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.
The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).
Implement the SnakeGame class:
SnakeGame(int width, int height, int[][] food)Initializes the object with a screen of sizeheight x widthand the positions of thefood.int move(String direction)Returns the score of the game after applying onedirectionmove by the snake. If the game is over, return-1.
Example 1:
Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]
Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border
Constraints:
1 <= width, height <= 1041 <= food.length <= 50food[i].length == 20 <= ri < height0 <= ci < widthdirection.length == 1directionis'U','D','L', or'R'.- At most
104calls will be made tomove.
Approach Overview
Problem Overview: Design a Snake Game that runs on a 2D grid. The snake moves in four directions, grows when it eats food, and the game ends if it hits the wall or its own body. You must implement efficient movement, food consumption, and self-collision detection.
Approach 1: List-Based Snake Simulation (O(n) time per move, O(n) space)
Store the snake body as a list of grid coordinates where the head is at the front and the tail at the end. Each move computes the new head position and checks whether the snake eats food. If food is eaten, keep the tail; otherwise remove the last element to simulate movement. To detect self-collision, iterate through the entire body list and check whether the new head overlaps an existing segment. This approach is simple and easy to implement but inefficient because every move may require scanning the entire snake body.
Approach 2: Deque + Hash Set for O(1) Simulation (O(1) time per move, O(n) space)
The optimal solution uses a deque to store the snake body order and a hash set for constant-time collision checks. The deque maintains the head and tail positions efficiently while the hash set stores encoded coordinates like row * width + col for fast lookup. On each move, compute the next head position based on the direction. If the new cell contains food, increase the score and keep the tail. Otherwise remove the tail from both the deque and the set before inserting the new head. Removing the tail first avoids falsely detecting a collision when the snake moves into the previous tail position.
The key insight is separating responsibilities: the deque handles ordered movement while the hash set handles fast membership checks. This avoids the O(n) scan required by the naive approach. Grid boundaries are checked before inserting the new head to detect wall collisions.
This design problem combines ideas from array-based coordinate systems, hash table lookups for collision detection, and queue-style body updates using a deque.
Recommended for interviews: The deque + hash set simulation is the expected solution. Interviewers want to see O(1) updates for movement and collision detection. Explaining the naive body scan first demonstrates understanding of the simulation, but implementing the hash-backed design shows strong data structure skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| List-Based Snake Body Simulation | O(n) per move | O(n) | Simple prototype or when snake size is very small |
| Deque + Hash Set (Optimal) | O(1) per move | O(n) | Interview-ready solution with constant-time movement and collision detection |
| Deque Only with Linear Collision Check | O(n) per move | O(n) | When avoiding extra hash storage but accepting slower collision checks |