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
- Represent the snake body as a deque of cells:
appendleftfor the new head,popfor the tail. - Also keep a hash set of occupied cells so self-collision is an O(1) test rather than an O(length) scan.
- 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.
- 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:
foodentries 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.