⌘K

Tutor

Leetcode 353. Design Snake Game

Asked at:

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

Forgetting to remove tail from hash set when snake doesn't eat food—causes false collision detection. Fix: Always sync deque and set operations.

Checking collision after updating position—the new head might overlap with the old tail that should be removed. Fix: Remove tail first (if not eating), then check collision.

Off-by-one errors in grid boundaries—using row >= m instead of row >= m. Fix: Carefully validate 0 ≤ row < m and 0 ≤ col < n.

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.

Solution

from collections import deque
from typing import List, Tuple
class SnakeGame:
    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.width = width
        self.height = height
        self.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.

Solution

    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 -1
        
        if self.food_queue and new_head == self.food_queue[0]:
            self.food_queue.popleft()
            self.score += 1
            self.snake.appendleft(new_head)
            self.occupied.add(new_head)
        else:
            if new_head in self.occupied:
                return -1
            self.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.

Solution

    def is_game_over(self) -> bool:
        return self.score == -1
    
    def get_score(self) -> int:
        return self.score if self.score != -1 else 0
    
    def 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.

Solution

# 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 -1
    return 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

Matrices

Lesson

Depth-First Search

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.

Learn

Rotting Oranges

medium

Breadth-First Search

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.

Practice

Spiral Matrix

medium

Matrices

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.

Practice

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late January, 2026

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 353. Design Snake Game

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Snake Body Representation and Initialization

Movement Logic and Collision Detection

Food Management and Game State

Complete Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact