LeetCode 353 - Design Snake Game

LeetCode Problem 353

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Queue, Simulation

Solution

Problem Understanding

The problem asks us to design a mutable data structure that simulates the classic Snake game. The game is played on a rectangular grid with dimensions height x width. The snake starts at the top-left corner (0, 0) and initially has length 1.

The game receives a predefined sequence of food positions. Only one food item exists on the board at a time. When the snake moves onto the current food position, two things happen:

1. The score increases by 1
2. The snake grows longer by one unit

The move(direction) operation advances the snake by one cell in the specified direction:

• "U" moves up
• "D" moves down
• "L" moves left
• "R" moves right

After each move, we must determine whether the snake is still alive. The game ends in two situations:

• The snake moves outside the grid boundaries
• The snake collides with its own body

The subtle part of the collision rule is extremely important. During a normal move, the snake's tail moves forward. This means the head is allowed to move into the cell currently occupied by the tail, because the tail vacates that position during the same move. Many incorrect implementations fail on this detail.

The input consists of:

• width and height, defining the board dimensions
• food, an ordered list of food coordinates
• Multiple calls to move(direction)

The output for each move is:

• The current score if the move is valid
• -1 if the move causes game over

The constraints tell us several important things:

• Up to 10^4 calls to move
• Grid dimensions can also be as large as 10^4
• Food count is relatively small, at most 50

Since there can be many move operations, each move must be efficient. A solution that scans the entire snake body on every move could become too slow if the snake grows large.

Several edge cases are important upfront:

• Moving into the wall
• Moving into the snake's own body
• Moving into the current tail position, which is actually valid during non-growth moves
• Eating food and growing correctly
• Handling the transition when no more food remains
• Maintaining the correct order of snake body segments

Approaches

Brute Force Approach

A straightforward implementation would explicitly store the snake body as a list of coordinates. On every move, we would:

1. Compute the new head position
2. Check wall collisions
3. Check self-collision by scanning the entire snake body
4. Insert the new head
5. Remove the tail if food was not eaten

This approach is correct because it directly simulates the game mechanics exactly as described.

However, self-collision detection becomes expensive. If the snake has length k, checking whether the new head overlaps the body requires O(k) time. Since there may be up to 10^4 move operations, the total runtime could become quadratic in the worst case.

Optimal Approach

The key insight is that collision detection should be constant time.

We need two capabilities simultaneously:

• Efficient insertion/removal from both ends of the snake body
• Fast membership testing to determine whether a coordinate is occupied

A deque is ideal for maintaining the snake order:

• Front represents the head
• Back represents the tail

A hash set is ideal for occupancy checking:

• O(1) average-time collision detection

The tricky part is handling movement into the tail cell correctly. During a normal move, the tail disappears before collision checking finishes. Therefore, we temporarily remove the tail from the set before checking whether the new head collides with the body.

This gives us constant-time movement operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k) per move	O(k)	Linear self-collision scan
Optimal	O(1) per move	O(k)	Uses deque plus hash set

Here, k is the current snake length.

Algorithm Walkthrough

1. Initialize the snake body with coordinate (0, 0).

We store the snake in a deque because we frequently add a new head and remove the tail. Both operations are efficient in a deque. 2. Store all occupied cells in a hash set.

The set allows constant-time collision detection. Each coordinate is encoded as either a tuple or a unique integer representation. 3. Maintain a food index pointer.

Since food appears sequentially, we only need to track which food item is currently active. 4. During each move, determine the new head position.

Based on the direction character, compute the next row and column. 5. Check wall collisions.

If the new coordinate lies outside the grid boundaries, return -1. 6. Determine whether the snake eats food.

Compare the new head coordinate with the current food coordinate. 7. If food is not eaten, remove the tail first.

This is the most important detail in the entire problem. The tail cell becomes empty during movement, so the head may legally move into that position. 8. Check self-collision using the hash set.

After the tail adjustment, if the new head already exists in the occupied set, the snake collided with itself and the game ends. 9. Add the new head to both the deque and hash set.

This updates the snake state after a successful move. 10. If food was eaten, advance the food pointer and increase the score.

In this case, the tail is not removed, which causes the snake to grow by one segment. 11. Return the current score.

Why it works

The algorithm maintains two synchronized representations of the snake:

• The deque preserves the exact order of body segments
• The hash set tracks occupied cells

Before collision checking, the tail is removed during non-growth moves. This accurately reflects the game rule that the tail moves away simultaneously with the head movement. Therefore, any collision detected afterward truly represents the head entering an occupied body cell.

Because every move updates both structures consistently, the snake state always remains correct.

Python Solution

from collections import deque
from typing import List, Deque, Set, Tuple

class SnakeGame:

    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0

        # Head is at the front
        self.snake: Deque[Tuple[int, int]] = deque([(0, 0)])

        # Stores occupied positions
        self.occupied: Set[Tuple[int, int]] = {(0, 0)}

        self.score = 0

    def move(self, direction: str) -> int:
        head_row, head_col = self.snake[0]

        if direction == "U":
            new_row, new_col = head_row - 1, head_col
        elif direction == "D":
            new_row, new_col = head_row + 1, head_col
        elif direction == "L":
            new_row, new_col = head_row, head_col - 1
        else:  # "R"
            new_row, new_col = head_row, head_col + 1

        # Check wall collision
        if (
            new_row < 0
            or new_row >= self.height
            or new_col < 0
            or new_col >= self.width
        ):
            return -1

        new_head = (new_row, new_col)

        # Check whether food is eaten
        eating_food = (
            self.food_index < len(self.food)
            and self.food[self.food_index] == [new_row, new_col]
        )

        # Remove tail first if not growing
        if not eating_food:
            tail = self.snake.pop()
            self.occupied.remove(tail)

        # Check self collision
        if new_head in self.occupied:
            return -1

        # Add new head
        self.snake.appendleft(new_head)
        self.occupied.add(new_head)

        # Handle food consumption
        if eating_food:
            self.food_index += 1
            self.score += 1

        return self.score

The implementation begins by storing board dimensions, food positions, and the current food index. The snake body is represented using a deque, with the head always stored at the front.

The occupied hash set mirrors the snake body positions. This allows constant-time collision checks.

Inside move, the first step is computing the next head coordinate based on the direction input. After that, the code immediately checks whether the move leaves the board.

The next important step determines whether the snake is eating food. This decision controls whether the tail should be removed. If the snake is not growing, the tail is removed before self-collision checking. This ensures that moving into the old tail position is allowed.

Once collision detection passes, the new head is inserted into both the deque and the set. Finally, if food was eaten, the score and food pointer are updated.

Go Solution

package main

type SnakeGame struct {
	width     int
	height    int
	food      [][]int
	foodIndex int
	score     int

	snake [][2]int
	body  map[[2]int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
	start := [2]int{0, 0}

	return SnakeGame{
		width:     width,
		height:    height,
		food:      food,
		foodIndex: 0,
		score:     0,
		snake:     [][2]int{start},
		body: map[[2]int]bool{
			start: true,
		},
	}
}

func (this *SnakeGame) Move(direction string) int {
	head := this.snake[0]

	newRow := head[0]
	newCol := head[1]

	switch direction {
	case "U":
		newRow--
	case "D":
		newRow++
	case "L":
		newCol--
	case "R":
		newCol++
	}

	// Wall collision
	if newRow < 0 || newRow >= this.height ||
		newCol < 0 || newCol >= this.width {
		return -1
	}

	newHead := [2]int{newRow, newCol}

	// Check if food is eaten
	eatingFood := false

	if this.foodIndex < len(this.food) {
		foodPos := this.food[this.foodIndex]

		if foodPos[0] == newRow && foodPos[1] == newCol {
			eatingFood = true
		}
	}

	// Remove tail if not growing
	if !eatingFood {
		tail := this.snake[len(this.snake)-1]
		this.snake = this.snake[:len(this.snake)-1]
		delete(this.body, tail)
	}

	// Self collision
	if this.body[newHead] {
		return -1
	}

	// Add new head
	this.snake = append([][2]int{newHead}, this.snake...)
	this.body[newHead] = true

	// Handle food
	if eatingFood {
		this.foodIndex++
		this.score++
	}

	return this.score
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * obj := Constructor(width, height, food)
 * param_1 := obj.Move(direction)
 */

The Go implementation follows the same logic as the Python version, but there are a few language-specific details.

Go does not provide a built-in deque, so the snake body is represented using a slice. The head is inserted at the front using slice concatenation. Given the problem constraints, this remains acceptable.

Coordinates are represented using fixed-size arrays [2]int, which are hashable and can therefore be used as keys in a map.

The occupancy structure uses map[[2]int]bool to simulate a hash set.

Worked Examples

Example 1

Input:

width = 3
height = 2
food = [[1,2],[0,1]]

Initial state:

State	Value
Snake	[(0,0)]
Score	0
Food Index	0
Current Food	(1,2)

Move 1: "R"

New head becomes (0,1).

No food eaten, so tail (0,0) is removed first.

State	Value
Snake	[(0,1)]
Score	0
Return	0

Move 2: "D"

New head becomes (1,1).

No food eaten.

State	Value
Snake	[(1,1)]
Score	0
Return	0

Move 3: "R"

New head becomes (1,2).

Food is eaten.

Tail is not removed because the snake grows.

State	Value
Snake	[(1,2), (1,1)]
Score	1
Return	1

The next food now appears at (0,1).

Move 4: "U"

New head becomes (0,2).

No food eaten, tail moves.

State	Value
Snake	[(0,2), (1,2)]
Score	1
Return	1

Move 5: "L"

New head becomes (0,1).

Food is eaten.

State	Value
Snake	[(0,1), (0,2), (1,2)]
Score	2
Return	2

Move 6: "U"

New head becomes (-1,1).

This is outside the board.

State	Value
Return	-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per move	Every operation uses constant-time deque and hash set operations
Space	O(k)	Stores snake body positions

Here, k is the current snake length.

The algorithm is efficient because no operation scans the snake body linearly. Collision detection uses hash lookups, and body updates only affect the head and tail.

Test Cases

# Provided example
game = SnakeGame(3, 2, [[1, 2], [0, 1]])
assert game.move("R") == 0  # normal move
assert game.move("D") == 0  # normal move
assert game.move("R") == 1  # eat first food
assert game.move("U") == 1  # move without eating
assert game.move("L") == 2  # eat second food
assert game.move("U") == -1  # wall collision

# Smallest possible board
game = SnakeGame(1, 1, [])
assert game.move("R") == -1  # immediate wall collision

# Eating food and growing
game = SnakeGame(2, 2, [[0, 1]])
assert game.move("R") == 1  # eat food
assert game.move("D") == 1  # continue moving

# Moving into old tail position should be allowed
game = SnakeGame(3, 2, [[0, 1], [0, 2]])
assert game.move("R") == 1  # eat first food
assert game.move("R") == 2  # eat second food
assert game.move("D") == 2  # move
assert game.move("L") == 2  # move
assert game.move("U") == 2  # move into old tail position

# Self collision
game = SnakeGame(3, 3, [[0,1],[0,2],[1,2],[1,1]])
assert game.move("R") == 1
assert game.move("R") == 2
assert game.move("D") == 3
assert game.move("L") == 4
assert game.move("U") == -1  # self collision

# No food at all
game = SnakeGame(2, 2, [])
assert game.move("R") == 0
assert game.move("L") == 0
assert game.move("D") == 0

# Vertical movement boundaries
game = SnakeGame(2, 2, [])
assert game.move("D") == 0
assert game.move("D") == -1  # bottom wall

# Horizontal movement boundaries
game = SnakeGame(2, 2, [])
assert game.move("R") == 0
assert game.move("R") == -1  # right wall

Test	Why
Provided example	Validates the full gameplay flow
1x1 board	Tests smallest board boundary
Food growth	Ensures snake length increases correctly
Move into old tail	Verifies the subtle collision rule
Self collision	Ensures body collision detection works
No food	Tests pure movement logic
Vertical wall collision	Tests lower boundary handling
Horizontal wall collision	Tests right boundary handling

Edge Cases

One important edge case occurs when the snake moves into the position currently occupied by its tail. A naive implementation may incorrectly treat this as self-collision. However, during a normal move, the tail moves away simultaneously. The implementation handles this by removing the tail from the occupancy set before collision detection when food is not eaten.

Another critical edge case is eating food. When the snake consumes food, the tail must not move during that turn. Forgetting this causes the snake length to remain unchanged. The implementation solves this by conditionally skipping tail removal whenever food is eaten.

Wall collisions are another common source of bugs. Since the board coordinates are zero-indexed, valid rows are [0, height - 1] and valid columns are [0, width - 1]. The implementation explicitly checks all four boundaries before updating the snake state.

A subtle scenario occurs when no food remains. Some implementations accidentally access beyond the end of the food list. The solution prevents this by checking food_index < len(food) before attempting food comparison.

Finally, maintaining synchronization between the deque and hash set is essential. Any inconsistency between them can produce impossible states where collision checks become incorrect. The implementation updates both structures together on every move, ensuring they always represent the same snake body.