Skip to main content
Talentd

Design Snake Game - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableDesignQueue8 min readAsked at: Amazon, Microsoft, Salesforce +7
Practice this problem

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 size height x width and the positions of the food.
  • int move(String direction) Returns the score of the game after applying one direction move 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 <= 104
  • 1 <= food.length <= 50
  • food[i].length == 2
  • 0 <= ri < height
  • 0 <= ci < width
  • direction.length == 1
  • direction is 'U', 'D', 'L', or 'R'.
  • At most 104 calls will be made to move.

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
List-Based Snake Body SimulationO(n) per moveO(n)Simple prototype or when snake size is very small
Deque + Hash Set (Optimal)O(1) per moveO(n)Interview-ready solution with constant-time movement and collision detection
Deque Only with Linear Collision CheckO(n) per moveO(n)When avoiding extra hash storage but accepting slower collision checks

Video Solution

LeetCode 353. Design Snake Game • Happy Coding • 10,863 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Design Snake Game easy or hard?
Design Snake Game is considered a medium difficulty problem. The movement simulation is straightforward, but handling self-collisions efficiently and managing the tail update order requires careful data structure design.
Design Snake Game Python/Java solution
The solution logic is identical across languages: maintain a deque for the body and a hash set for occupied cells. Python uses collections.deque and a set, while Java typically uses ArrayDeque and HashSet. Both implementations achieve O(1) time per move.
How to solve Design Snake Game in O(1)?
Maintain the snake body using a deque and track occupied positions with a hash set. On each move, compute the new head coordinate, remove the tail if no food is eaten, and check the hash set for collisions. Updating both structures keeps every move operation constant time.
What is the best approach for Design Snake Game?
The best approach uses a deque to maintain the snake body order and a hash set to track occupied cells. The deque supports efficient head insertion and tail removal, while the hash set enables O(1) collision detection. Each move runs in constant time, which is required for large numbers of operations.
Is Design Snake Game asked at Google/Amazon/Meta?
Design-style simulation problems like Design Snake Game frequently appear in interviews at large tech companies including Amazon and Google. The problem tests data structure design, efficient simulation, and edge-case handling such as collisions and boundary checks.
What data structure is used in Design Snake Game?
The core data structures are a deque (or queue) for maintaining the snake's body order and a hash set for fast collision detection. The grid coordinates are usually encoded into a single integer to simplify storage and lookup.
What is the time complexity of Design Snake Game?
The optimal implementation runs in O(1) time per move. Deque operations for adding the head and removing the tail are constant time, and hash set lookups detect collisions in O(1). Space complexity is O(n), where n is the current snake length.

Ready to solve this problem?

Practice Design Snake Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays