⚡Flashcard Drill➔
NeetCode #32LC-353MediumArrays & HashingNC Algo100
← Back to All Problems

#32 · #353 · Design Snake Game(贪吃蛇游戏)

📌 Problem Statement & Constraints

Design a Snake game on a width x height grid. The snake starts at (0, 0) with length 1. Food positions are given in advance. Implement move(direction) returning the current score, or -1 if the snake runs into a wall or into itself. Constraints: 1 <= width, height <= 10^4, 1 <= food.length <= 50.

💡 Core Algorithmic Approaches

  1. Represent the snake body as a deque of cells: appendleft for the new head, pop for the tail.
  2. Also keep a hash set of occupied cells so self-collision is an O(1) test rather than an O(length) scan.
  3. The critical subtlety: when the snake does not eat, the tail vacates its cell in the same step, so the new head may legally move into the old tail position. Therefore remove the tail before the collision check.
  4. When the snake does eat, the tail stays put and the length grows by one; the score increments and the food index advances.

💻 Benchmark Python3 Implementation

class SnakeGame:
    def __init__(self, width: int, height: int, food: List[List[int]]):
        from collections import deque
        self.w, self.h = width, height
        self.food = food
        self.food_i = 0
        self.score = 0
        self.body = deque([(0, 0)])        # head at index 0
        self.occupied = {(0, 0)}

    def move(self, direction: str) -> int:
        dr, dc = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}[direction]
        hr, hc = self.body[0]
        nr, nc = hr + dr, hc + dc

        if not (0 <= nr < self.h and 0 <= nc < self.w):
            return -1                      # hit a wall

        eating = (self.food_i < len(self.food)
                  and [nr, nc] == self.food[self.food_i])
        if not eating:
            tail = self.body.pop()         # tail vacates BEFORE the collision test
            self.occupied.discard(tail)

        if (nr, nc) in self.occupied:
            return -1                      # hit itself

        self.body.appendleft((nr, nc))
        self.occupied.add((nr, nc))
        if eating:
            self.score += 1
            self.food_i += 1
        return self.score

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per move: deque operations plus a hash-set membership test.
💾 Space Complexity
O(length) for the body deque and the occupied set.

⚠️ Interview Pitfalls & Follow-ups

  • Checking the collision before removing the tail: the snake may legally move into the cell its tail is vacating this very step, so the order matters. This is the classic bug in this problem.
  • Scanning the deque for self-collision: O(length) per move; the occupied set makes it O(1).
  • Forgetting to remove the tail from occupied: stale cells would cause spurious collisions later.
  • Growing the snake on every move: the length increases only when food is eaten.
  • Comparing food as a tuple against a list: food entries are lists, so compare [nr, nc] == food[i] (or normalise both to tuples).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems