353. Design Snake Game - Detailed Explanation

In this optimized Java code, we encoded the (row, col) positions into a single integer row * width + col before storing in the occupied set. This avoids needing a custom object for coordinates. We also carefully remove the tail from the set before checking for collisions with the new head (except when eating). The logic ensures each move is handled in constant time.

Space Optimization: If memory is a concern in another context, note that we maintain two data structures for the snake’s body (deque and set). This is slightly redundant since the same information is stored twice (once in order, once for quick lookup). However, the space overhead is minimal for a small snake. In a scenario with a very long snake, one might attempt to use a specialized data structure that can support fast lookup and popping from ends in one structure (for example, a linked list with a hash set of references, which is essentially what we have). The chosen approach is straightforward and clear in intent.

Step-by-Step Walkthrough

Let's walk through an example step by step to visualize how the snake moves and how our data structures update. We’ll use Example 1 (grid 3×2 with two foods) to illustrate:

Initial State:

• Snake at (0,0) (length=1, occupies top-left cell).
• Food list = [(1,2), (0,1)], so the first food is at (1,2) (bottom-right cell).
• Score = 0.
• Data Structures: snake = [(0,0)]; occupied = {(0,0)}.

Grid view:

|S| | |   <- Snake at (0,0)
| | |F|   <- Food at (1,2)

Move 1: "R" (Right)

• New head: from (0,0) to (0,1).
• Bounds check: (0,1) is within the grid.
• Food check: (0,1) is not at food (first food is at (1,2)), so eating = False.
• Tail removal: Snake not eating, remove tail. Tail was (0,0), so remove it from snake list/deque and from occupied. Now snake becomes empty temporarily, and occupied becomes empty.
• Collision check: Is (0,1) in occupied? Currently no (occupied is empty after tail removal), so no self-collision.
• Add new head: Prepend (0,1) to snake and add to occupied. Now snake = [(0,1)], occupied = {(0,1)}.
• Score: remains 0 (no food eaten).

Grid after move 1:

| |S| |   <- Snake moved to (0,1)
| | |F|   <- Food still at (1,2)

Move 2: "D" (Down)

• Current head is (0,1). New head goes down to (1,1).
• (1,1) is inside grid, OK.
• Food check: first food is at (1,2), not at (1,1), so no eating.
• Tail removal: Remove tail (which is currently at (0,1)) from snake and occupied. Now snake becomes empty, occupied empty.
• Collision check: (1,1) in occupied? No (occupied is empty).
• Add new head: snake = [(1,1)], occupied = {(1,1)}.
• Score stays 0.

Grid after move 2:

| | | |   
| |S|F|   <- Snake at (1,1), food at (1,2)

Move 3: "R" (Right)

• Head (1,1) → new head (1,2).
• (1,2) is within bounds.
• Food check: (1,2) matches the first food location. So eating = True. This means the snake will grow. We increment score to 1 and advance food_index to point to the next food (which is (0,1)).
• Tail removal: Skip removing tail because snake is eating. (The tail at (1,1) will remain as part of the snake’s body.)
• Collision check: Check if (1,2) is in occupied. Currently, occupied = {(1,1)} and we did not remove (1,1) since we are eating. (1,2) is not in {(1,1)}, so no collision.
• Add new head: snake becomes [(1,2), (1,1)] (we add (1,2) to the front, and (1,1) remains as tail), occupied becomes {(1,2), (1,1)}.
• Score is now 1. A new food appears at the next position (0,1) (as given by the food list).

Grid after move 3:

| |F| |   <- New food appears at (0,1)
| |S|S|   <- Snake now occupies (1,2) and (1,1)

(Snake’s head is at (1,2) and tail at (1,1).)

Move 4: "U" (Up)

• Head (1,2) → new head (0,2).
• (0,2) in bounds.
• Food check: Next food is at (0,1), not at (0,2), so no eating.
• Tail removal: Remove tail (currently (1,1)) from snake and occupied. Now snake = [(1,2)], occupied = {(1,2)}.
• Collision check: Is (0,2) in occupied? occupied = {(1,2)}, so no.
• Add new head: snake = [(0,2), (1,2)], occupied = {(0,2), (1,2)}.
• Score remains 1. (The food at (0,1) is still on the board.)

Grid after move 4:

| |F|S|   <- Snake head moved to (0,2); food at (0,1)
| | |S|   <- Snake tail now at (1,2)

Move 5: "L" (Left)

• Head (0,2) → new head (0,1).
• (0,1) in bounds.
• Food check: (0,1) matches the next food. eating = True. Score becomes 2, and we mark that there are no more foods (food_index now beyond list length).
• Tail removal: Skip (snake will grow). Tail (which is at (1,2)) stays.
• Collision check: occupied = {(0,2), (1,2)} (snake body before move). (0,1) is not in that set, so no collision.
• Add new head: snake becomes [(0,1), (0,2), (1,2)], occupied = {(0,1), (0,2), (1,2)}.
• Score = 2. No more food on grid now.

Grid after move 5:

| |S|S|   <- Snake occupies (0,1) and (0,2) in top row
| | |S|   <- Snake occupies (1,2) in bottom row

(Snake’s head at (0,1), body at (0,2), tail at (1,2).)

Move 6: "U" (Up)

• Head (0,1) → new head (-1,1).
• New head is out of bounds (row = -1 is above the top row).
• We detect the wall collision immediately. The move returns -1, and the game is over. The snake does not actually move because the game ended.

In the step-by-step, we saw how the snake’s body list/deque and occupied set are updated on each move. Notably:

• When the snake eats food, we did not remove the tail, resulting in the snake’s length increasing.
• When the snake moves without eating, the tail cell is freed up (removed from the occupied set) before placing the new head.
• Collision checks are always done after accounting for the tail movement, which handles the scenario of the snake moving into its own tail’s previous position correctly.

Common Mistakes & Edge Cases

Common Pitfalls:

• Removing Tail at the Wrong Time: A very common mistake is to check for self-collision before removing the tail on a non-eating move. For example, imagine the snake’s head is moving into the cell that was just occupied by its tail. If you haven’t removed the tail from the data structure and you check for collision, you’ll incorrectly think the snake ran into itself. Always remove or account for the tail leaving before checking if the new head hits the body. In our solution, we handle this by either removing the tail first (on non-eat moves) or by allowing the tail to stay only when eating.

• Not Updating Food Index: Forgetting to move to the next food after the snake eats one. If you don’t update the food index (or remove the eaten food from the list), the snake might keep “eating” the same food repeatedly in your logic. Our implementations increment food_index or pop from the food list when food is eaten.

• Boundary Conditions: Off-by-one errors in checking boundaries. Remember that valid row indices are 0 to height-1 and valid column indices are 0 to width-1. A head position equal to height or width is out of bounds (since indexing is 0-based). We explicitly check these conditions.

• Using a Grid Matrix: Some might try to use a 2D grid matrix of size height x width to mark the snake’s presence. This is unnecessary and can be extremely memory-intensive for large grids (up to 100 million cells). It’s both inefficient and not needed – use a set for occupied cells instead.

• Mutable State Bugs: If using linked structures or queues, be careful about modifying them. For instance, in Python, doing head = self.snake[0] and then modifying self.snake could make head outdated. We handle moves carefully by computing the new head in local variables first.

Edge Cases to Consider:

• No Food Scenario: If food list is empty, the snake will never grow. The game reduces to just moving until hitting a wall or itself. Our logic handles this since food_index < len(food) will be false from the start, and the snake will just move with tail always being removed.

• Single Cell Grid: If width = height = 1, the snake starts in the only cell. Any move will go out of bounds immediately. The first move should return -1 (game over). Also, no food can appear at (0,0) initially because the snake occupies it (and the problem guarantee says food won’t spawn on the snake). If a test did give food = [(0,0)] with a 1x1 grid (which would violate that guarantee), the snake would technically eat it at start without moving, but such a scenario shouldn’t occur by problem design

• Immediate Self-Collision Move: If the snake has length > 1, the game (or tester) might try to move it in the direction directly opposite to its current direction. In a real snake game, this is usually disallowed because the snake cannot instantly reverse, but the problem doesn’t forbid the input from doing that. For example, if a snake is currently at [(0,1), (0,0)] (head at 0,1 and tail at 0,0), and the next move is "L" (left), the new head would go to (0,0). Our logic handles this correctly: since the snake is not eating, we remove the tail (which was at (0,0)) before checking collision, so moving into (0,0) is actually safe (it becomes the new head as the tail left). If the snake were longer and the move is a 180-degree turn, then the head would run into what was the second segment (since the tail wouldn’t be the one freeing up). Our collision check would catch that and return -1. So the key is our method naturally handles even “immediate U-turn” moves via the tail removal mechanism.

• Consuming Last Food: When the snake eats the last food in the list, make sure your code still behaves correctly on subsequent moves (no more food to eat, so it should just move normally with tail removal). Our implementations check food_index < len(food) to ensure we don't access out of range. After the last food is eaten, food_index == len(food) and the eating condition will be false for future moves, meaning the snake will just move without growing further.

Alternative Variations & Related Problems

Similar Design Problems on LeetCode: If you enjoyed solving the Snake Game, there are other design or simulation problems that test similar skills in managing state and ensuring efficient updates:

• 348. Design Tic-Tac-Toe: Design a Tic-Tac-Toe game class with a method to make moves and check for winners. It involves tracking game state on a grid, somewhat like how we track the snake on a grid.
• 362. Design Hit Counter: Design a hit counter that records hits and returns the number of hits in the past 5 minutes. It also uses a queue to efficiently drop old data, conceptually similar to removing the snake’s tail as time moves on.
• 359. Logger Rate Limiter: Another design problem where you need to decide if a message should be printed based on timestamps (can use a queue or hash map for recent messages).
• 146. LRU Cache: While not a game, it involves designing a data structure (Least Recently Used cache) that uses a combination of a deque (or linked list) and a hash map to achieve O(1) updates – very similar to the deque+set approach we used for the snake.
• 379. Design Phone Directory: Design a phone number directory with methods to get, check, and release numbers. It requires managing available and taken slots, which can be done with queues/sets as well.

Variations of Snake Game: The classic snake game can have different rules or enhancements. Consider how the solution might change under these variations:

• Multiple Food at Once: If more than one food could be present simultaneously (not the case in our problem, where one food appears at a time), we’d likely store all food positions in a set and check if the new head hits any food in that set, instead of using a single index. Eating would involve removing that food from the set and possibly spawning a new food if needed.

• Grid with Obstacles: If the grid had obstacles or forbidden cells, we would treat those similar to how we treat the snake’s body for collisions – e.g., have an additional set of obstacle cells and check that the snake’s head doesn’t land on one.

• Wrap-around Walls: In some versions of Snake, going off one edge makes you appear on the opposite edge (a toroidal board). To handle that, the move logic would change the boundary check: instead of game over, you’d compute the head position modulo width/height (wrap it around). Collision with itself can still happen in this scenario if the snake’s body occupies the wrapped cell.

• Snake Growth Mechanics: Our implementation grows the snake instantly by 1 when it eats. Some games might grow the snake gradually over subsequent moves. In that case, you might queue up growth events (e.g., “grow by 1 in the next move”) instead of growing immediately. This complicates the logic slightly, but conceptually you would delay the tail removal for a number of moves.