Leetcode 353. Design Snake Game
Asked at:
Meta
Palantir
Atlassian
Apple
DESCRIPTION
Implement a Snake game on an m×n grid where the snake moves in four directions, grows when eating food placed sequentially, and the game ends on collision with walls or its own body. The move(direction) method should advance the snake one cell, handle food consumption (incrementing score), and detect game-over conditions. For example, on a 3×3 grid with food at [(1,2), (0,1)], moving right then up should grow the snake twice before hitting a wall.
Input:
Grid: 3×3, Food: [(1,2), (0,1)] Initial snake: [(0,0)] (head at top-left) Moves: RIGHT, RIGHT, UP
Output:
After RIGHT: snake=[(0,1), (0,0)], score=0 After RIGHT: snake=[(0,2), (0,1), (0,0)], score=1 (ate food at (0,2)... wait, food is at (1,2)) After RIGHT: snake=[(0,2), (0,1)], score=0 After UP: Game Over (hit wall)
Explanation: Snake moves right twice (no food eaten), then moving up hits the top wall and ends the game.
Constraints:
- 1 ≤ m, n ≤ 10^4 (grid dimensions)
- Snake starts at (0,0) with length 1
- Food positions are given in sequential order
- move() is called up to 10^4 times
- Directions: UP, DOWN, LEFT, RIGHT
Understanding the Problem
The core challenge is efficiently tracking the snake's body as it moves, grows, and potentially collides with itself. Each move() call requires: (1) computing the new head position, (2) checking for collisions with walls or body, (3) determining if food is eaten (grow) or not (remove tail), and (4) updating the occupied cells. With up to 10^4 moves on large grids, O(1) collision detection is critical, requiring a hash set to track occupied cells alongside a deque for the ordered body segments.
Building Intuition
A naive approach stores the snake body as a list and checks collisions by iterating through all segments—this becomes O(n) per move where n is snake length, potentially O(10^4) operations per move. The optimal approach uses a deque for the ordered body (efficient head insertion and tail removal) plus a hash set for occupied cells (O(1) collision checks). For example, moving right on a snake [(2,3), (2,2), (2,1)] means adding (2,4) to the deque front and set, then removing (2,1) from both if no food is eaten.
This pattern of dual data structures (ordered sequence + membership set) appears in many real-time systems: browser history with fast lookup, LRU caches, and game state management. The Snake game specifically teaches state synchronization—keeping the deque and set consistent across insertions/deletions—which is fundamental to building reliable interactive applications.
Common Pitfalls
Implementation
Snake Body Representation and Initialization
Design the core data structures to represent the snake and grid state. Use a deque to store body segments in order (head at front) for efficient O(1) insertion/removal at both ends, and a set to track occupied cells for O(1) collision detection. Store the food queue and current score. For example, initializing a 4×4 grid with food at [(2,1), (3,2)] creates a snake at [(0,0)] with the set containing {(0,0)} and a food queue ready to dispense positions sequentially.
from collections import dequefrom typing import List, Tupleclass SnakeGame:def __init__(self, width: int, height: int, food: List[List[int]]):self.width = widthself.height = heightself.snake = deque([(0, 0)])self.occupied = {(0, 0)}self.food_queue = deque([(f[0], f[1]) for f in food])self.score = 0
Movement Logic and Collision Detection
Implement the move(direction) method to compute the new head position based on direction deltas, then check for wall collisions (out of bounds) and self-collisions (new head in occupied set). If valid, handle food consumption: if the new head matches the next food position, grow the snake (add head, keep tail, increment score); otherwise, move the snake (add head, remove tail from both deque and set). For example, moving RIGHT from (2,3) to (2,4) with food at (2,4) grows the snake to length 4 without removing the tail.
def move(self, direction: str) -> int:directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}dr, dc = directions[direction]head_r, head_c = self.snake[0]new_head = (head_r + dr, head_c + dc)if not (0 <= new_head[0] < self.height and 0 <= new_head[1] < self.width):return -1if self.food_queue and new_head == self.food_queue[0]:self.food_queue.popleft()self.score += 1self.snake.appendleft(new_head)self.occupied.add(new_head)else:if new_head in self.occupied:return -1self.snake.appendleft(new_head)self.occupied.add(new_head)tail = self.snake.pop()self.occupied.remove(tail)return self.score
Food Management and Game State
Manage the sequential food queue and game-over state to complete the game logic. Track the current food index to determine which food item is active, and set a game-over flag when collisions occur to prevent further moves. Provide a method to check if the game is still active and retrieve the current score. For example, after eating food at index 0, increment the food index so the next move() checks against food at index 1, ensuring food is consumed in the given order.
def is_game_over(self) -> bool:return self.score == -1def get_score(self) -> int:return self.score if self.score != -1 else 0def get_food_count(self) -> int:return len(self.food_queue)def get_snake_length(self) -> int:return len(self.snake)
Complete Integration
Combine the body representation (Section 1), movement logic (Section 2), and food management (Section 3) into a unified SnakeGame class. The constructor initializes the grid dimensions, food queue, and starting snake position. The move() method orchestrates collision detection, position updates, and food consumption, returning the current score or -1 on game over. For example, instantiate SnakeGame(4, 4, [(2,1), (3,2)]) and call move('RIGHT') repeatedly to simulate gameplay, with the class maintaining all state internally across moves.
# Complete Integration - All components are already unified in the SnakeGame class above# Usage example showing how to instantiate and use the complete system:def create_game(width: int, height: int, food: List[List[int]]) -> SnakeGame:"""Factory function to create a new SnakeGame instance."""return SnakeGame(width, height, food)def play_moves(game: SnakeGame, moves: List[str]) -> int:"""Execute a sequence of moves and return final score."""for direction in moves:score = game.move(direction)if score == -1:return -1return game.get_score()
What We've Learned
- Pattern: Dual data structures (deque + hash set) enable O(1) operations for ordered sequences with fast membership checks.
- Use Case: Real-time game state management, browser history, LRU caches—any system needing ordered tracking with collision detection.
- Synchronization: Always update both structures atomically (add/remove from deque and set together) to maintain consistency.
- Boundary Validation: Check collisions before finalizing state changes to avoid corrupting game state with invalid moves.
Problems to Practice
This lesson covers matrix traversal fundamentals which are essential for the Snake game's grid-based movement system. Understanding how to navigate and track positions in a 2D grid is directly applicable to implementing the snake's body tracking and collision detection.
medium
This problem involves tracking state changes in a grid over time with multiple entities, similar to tracking the snake's body segments as they move through the grid. Both require efficient position tracking and state management in a matrix structure.
medium
This problem requires systematic traversal and boundary checking in a matrix, which parallels the Snake game's need to track valid moves, detect wall collisions, and manage directional movement within grid boundaries.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late April, 2026
Atlassian
Senior
Late January, 2026
Meta
Mid-level
Late January, 2026
Palantir
Senior
Hello Interview Premium
Your account is free and you can post anonymously if you choose.