LeetCode Solutions Blog

Design Snake Game

Number: 353

Difficulty: Medium

Paid? Yes

Problem Description

Design a Snake game that is played on a board of size height x width. The snake starts at position (0, 0) with a length of 1 unit. You are given a list of food positions that appear one after the other. Each time the snake eats food, its length increases and so does the score. The game ends if the snake hits the wall or its own body (after moving).

Key Insights

Use a deque (or linked list) to represent the snake’s body, where the head is at one end.
Maintain a set for quick O(1) lookups to check if the snake collides with itself.
When moving, compute the new head position using a direction map.
Be careful when the snake eats food: do not remove the tail so the snake grows.
For non-food moves, remove the tail before checking for collisions so that the tail cell becomes available.

Space and Time Complexity

Time Complexity: O(1) per move since each move involves a constant number of operations. Space Complexity: O(N + F) where N is the snake length (which is at most the number of moves) and F is the fixed number of food items.

Solution

The solution involves simulating the snake’s movement on the board. We store the snake’s positions in a deque, and a hash set is used to quickly check for collisions with its own body. Every call to move determines the new head position based on the input direction. We then check if the new position is out-of-bounds or if it collides with the snake itself (taking into account that if no food is eaten the tail is removed first). If the snake eats food, we increase the score and keep the tail intact to simulate growth. Otherwise, we remove the tail to keep the snake’s length constant. This strategy handles the simulation efficiently with constant time operations for each move.

Code Solutions

from collections import deque

class SnakeGame:
    def __init__(self, width, height, food):
        # Initialize board dimensions, food list, and game variables.
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0  # Tracks the next food item to eat.
        self.score = 0
        
        # Use deque to represent the snake; head is the last element.
        self.snake = deque([(0, 0)])
        # Set for constant time collision checks.
        self.snake_set = set([(0, 0)])
        
        # Map directions to their coordinate changes.
        self.directions = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
    
    def move(self, direction):
        # Get current head position.
        head_row, head_col = self.snake[-1]
        delta_row, delta_col = self.directions[direction]
        new_head = (head_row + delta_row, head_col + delta_col)
        
        # Check if the new head position is outside the board.
        r, c = new_head
        if r < 0 or r >= self.height or c < 0 or c >= self.width:
            return -1
        
        # Determine if we have food at the new head position.
        eating_food = (self.food_index < len(self.food) and [r, c] == self.food[self.food_index])
        
        # If not eating food, remove the tail (simulate movement).
        tail = self.snake[0]
        if not eating_food:
            self.snake.popleft()
            self.snake_set.remove(tail)
        else:
            # Eating food increases score and move to the next food item.
            self.food_index += 1
            self.score += 1
        
        # Check for collision with its body.
        if new_head in self.snake_set:
            return -1
        
        # Add the new head position.
        self.snake.append(new_head)
        self.snake_set.add(new_head)
        
        return self.score