Problem Description

This problem asks you to implement a Snake game with the following rules and requirements:

Game Setup:

• The game is played on a screen with dimensions height x width
• The snake starts at position (0, 0) (top-left corner) with length 1
• Food items are provided as an array where food[i] = (ri, ci) represents the row and column position of the i-th food piece

Game Mechanics:

• When the snake eats food, both its length and the game score increase by 1
• Food appears one at a time - the next food item only appears after the current one is eaten
• Food is guaranteed to never appear on a position occupied by the snake

Game Over Conditions:

• The snake moves out of bounds (hits a wall)
• The snake's head collides with its own body after moving

Implementation Requirements:

You need to implement a SnakeGame class with two methods:

1. SnakeGame(int width, int height, int[][] food): Constructor that initializes the game with the screen dimensions and food positions

2. int move(String direction): Processes one move in the given direction ("U" for up, "D" for down, "L" for left, "R" for right) and returns:

   • The current score if the move is valid
   • -1 if the game is over (snake hits wall or itself)

The key challenge is tracking the snake's body positions efficiently while handling the growth when eating food and checking for self-collision. The snake moves by adding a new head position in the direction of movement and removing the tail (unless food is eaten, in which case the tail remains to increase length).

Intuition

The key insight for solving this problem is understanding how a snake moves in the classic game. When a snake moves, it doesn't actually move every segment - instead, it adds a new head in the direction of movement and removes its tail. This creates the illusion of movement while being computationally efficient.

Think about it this way: if the snake is 5 units long and moves right, we don't need to update all 5 positions. We just:

1. Add a new head to the right of the current head
2. Remove the tail (unless food was just eaten)

This observation leads us to use a deque (double-ended queue) data structure, which allows efficient addition at the front (new head) and removal from the back (tail).

For collision detection, we need to quickly check if a position is occupied by the snake's body. A set is perfect for this - it gives us O(1) lookup time to check if the new head position would collide with any part of the body.

The special case of eating food is handled elegantly: when the snake's new head position matches the current food position, we simply skip removing the tail. This naturally increases the snake's length by one unit.

The order of operations is crucial to avoid false collisions:

1. First, calculate where the new head would be
2. Check if it's out of bounds (wall collision)
3. Check if it's food - if yes, eat it (increment score and food index)
4. If not food, remove the tail from both the deque and the set
5. Check if the new head position collides with the body (now that tail is removed if needed)
6. Finally, add the new head to both the deque and the set

This sequence ensures that the snake can move into the space its tail just vacated, which is a valid move in the game.

Solution Approach

The implementation uses a deque and a set to efficiently manage the snake's movement and collision detection.

Data Structures:

• self.q: A deque that stores the snake's body positions as (row, column) tuples, with the head at index 0
• self.vis: A set that stores all positions occupied by the snake for O(1) collision checking
• self.food: Array of food positions
• self.idx: Current food index to track which food item should appear next
• self.score: Current game score

Initialization (__init__ method):

self.q = deque([(0, 0)])  # Snake starts at top-left
self.vis = {(0, 0)}       # Mark initial position as occupied
self.score = 0            # Initial score
self.idx = 0              # Start with first food item

Move Implementation (move method):

1. Get current head position and calculate new position:

   i, j = self.q[0]  # Current head position
   x, y = i, j       # New position (to be updated based on direction)

2. Update position based on direction using pattern matching:

   match direction:
       case "U": x -= 1  # Move up (decrease row)
       case "D": x += 1  # Move down (increase row)
       case "L": y -= 1  # Move left (decrease column)
       case "R": y += 1  # Move right (increase column)

3. Check boundary collision:

   if x < 0 or x >= self.m or y < 0 or y >= self.n:
       return -1  # Game over - hit wall

4. Handle food consumption or normal movement:

   if (self.idx < len(self.food) and
       x == self.food[self.idx][0] and
       y == self.food[self.idx][1]):
       # Food eaten - increase score and move to next food
       self.score += 1
       self.idx += 1
   else:
       # No food - remove tail (snake doesn't grow)
       self.vis.remove(self.q.pop())

5. Check self-collision:

   if (x, y) in self.vis:
       return -1  # Game over - snake hit itself

6. Add new head position:

   self.q.appendleft((x, y))  # Add to front of deque
   self.vis.add((x, y))       # Mark position as occupied
   return self.score

Time Complexity:

• move(): O(1) for all operations (deque append/pop, set add/remove/lookup)

Space Complexity:

• O(N) where N is the maximum length of the snake (at most width × height)

The elegance of this solution lies in how the deque naturally models the snake's movement pattern, while the set provides efficient collision detection. The careful ordering of operations ensures correct game logic, particularly allowing the snake to move into the space its tail just vacated.

Example Walkthrough

Let's walk through a small example with a 3×3 grid and food at positions [(1,2), (2,0)].

Initial Setup:

• Grid: 3×3 (height=3, width=3)
• Snake starts at (0,0) with length 1
• Food sequence: [(1,2), (2,0)]

Initial state:
[S][ ][ ]   S = Snake head
[ ][ ][F]   F = Food at (1,2)
[ ][ ][ ]   Score = 0

Move 1: move("R") - Move right

1. Current head: (0,0), calculate new position: (0,1)
2. Check bounds: 0≤0<3 and 0≤1<3 ✓
3. Not food position, remove tail from (0,0)
4. Check collision: (0,1) not in body ✓
5. Add new head at (0,1)

[ ][S][ ]   Score = 0
[ ][ ][F]
[ ][ ][ ]

Move 2: move("D") - Move down

1. Current head: (0,1), new position: (1,1)
2. Check bounds: ✓
3. Not food, remove tail
4. No collision ✓
5. Add new head at (1,1)

[ ][ ][ ]   Score = 0
[ ][S][F]
[ ][ ][ ]

Move 3: move("R") - Move right (eat food!)

1. Current head: (1,1), new position: (1,2)
2. Check bounds: ✓
3. Food at (1,2)! Score increases, don't remove tail
4. No collision ✓
5. Add new head at (1,2)

[ ][ ][ ]   Score = 1
[ ][B][S]   B = Body, S = Head
[F][ ][ ]   Next food appears at (2,0)
Snake length = 2

Move 4: move("D") - Move down

1. Current head: (1,2), new position: (2,2)
2. Check bounds: ✓
3. Not food, remove tail from (1,1)
4. No collision ✓
5. Add new head at (2,2)

[ ][ ][ ]   Score = 1
[ ][ ][B]
[F][ ][S]   Snake: (2,2)→(1,2)

Move 5: move("L") - Move left

1. Current head: (2,2), new position: (2,1)
2. Check bounds: ✓
3. Not food, remove tail from (1,2)
4. No collision ✓
5. Add new head at (2,1)

[ ][ ][ ]   Score = 1
[ ][ ][ ]
[F][S][B]   Snake: (2,1)→(2,2)

Move 6: move("L") - Move left (eat food!)

1. Current head: (2,1), new position: (2,0)
2. Check bounds: ✓
3. Food at (2,0)! Score increases, don't remove tail
4. No collision ✓
5. Add new head at (2,0)

[ ][ ][ ]   Score = 2
[ ][ ][ ]
[S][B][B]   Snake: (2,0)→(2,1)→(2,2)
             Length = 3

Move 7: move("U") - Move up (collision example)

1. Current head: (2,0), new position: (1,0)
2. Check bounds: ✓
3. Not food, remove tail from (2,2)
4. No collision ✓
5. Add new head at (1,0)

[ ][ ][ ]   Score = 2
[S][ ][ ]
[B][B][ ]   Snake: (1,0)→(2,0)→(2,1)

Move 8: move("U") - Move up (wall collision)

1. Current head: (1,0), new position: (0,0)
2. Check bounds: ✓
3. Not food, remove tail from (2,1)
4. No collision ✓
5. Add new head at (0,0)

[S][ ][ ]   Score = 2
[B][ ][ ]
[B][ ][ ]   Snake: (0,0)→(1,0)→(2,0)

Move 9: move("U") - Invalid move (hits wall)

1. Current head: (0,0), new position: (-1,0)
2. Check bounds: -1 < 0 - Out of bounds!
3. Return -1 (Game Over)

This example demonstrates:

• Normal movement (removing tail)
• Food consumption (keeping tail to grow)
• Boundary checking
• How the deque and set work together to track the snake efficiently

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(1) - Initializes the game with constant time operations. Creating a deque with one element and a set with one element are both O(1) operations.
• move: O(1) - Each move operation performs:
  • Direction calculation: O(1)
  • Boundary checking: O(1)
  • Food checking: O(1)
  • Adding/removing from deque: O(1) for both appendleft and pop
  • Adding/removing from set: O(1) average case for both operations
  • Checking membership in set: O(1) average case

Space Complexity:

• O(W × H) in the worst case, where W is the width and H is the height of the game board.
• The space is primarily used by:
  • self.q (deque): Can grow up to size W × H if the snake fills the entire board
  • self.vis (set): Maintains the same positions as the deque, so also up to W × H elements
  • self.food: O(F) where F is the number of food items, but this is typically much smaller than W × H
• In practice, the space complexity is O(min(S, W × H)) where S is the current length of the snake, since the snake's body occupies S cells at any given time.

Common Pitfalls

1. Incorrect Order of Tail Removal and Self-Collision Check

The Pitfall: A critical bug occurs if you check for self-collision before removing the tail when the snake doesn't eat food. This creates a false collision when the snake moves into the space its tail is vacating.

Incorrect Implementation:

def move(self, direction: str) -> int:
    # Calculate new head position...
    new_row, new_col = ...

    # Check self-collision FIRST (WRONG!)
    if (new_row, new_col) in self.occupied_positions:
        return -1

    # Then handle food/tail removal
    if food_eaten:
        self.score += 1
    else:
        tail = self.snake.pop()
        self.occupied_positions.remove(tail)

Why It Fails: When the snake moves into its tail's current position (a valid move), the collision check happens before the tail is removed, causing a false game over.

Example Scenario:

• Snake: [(1,1), (1,2), (2,2), (2,1)] forming a square
• Move: "L" (left)
• New head would be at (2,1) - currently the tail
• If checked before tail removal: Game Over (incorrect!)
• If tail removed first: Valid move

Correct Solution:

def move(self, direction: str) -> int:
    # Calculate new head position
    new_row, new_col = ...

    # Check boundary first
    if out_of_bounds:
        return -1

    # Remove tail BEFORE collision check (if no food)
    if food_eaten:
        self.score += 1
    else:
        tail = self.snake.pop()
        self.occupied_positions.remove(tail)

    # NOW check for self-collision
    if (new_row, new_col) in self.occupied_positions:
        return -1

    # Add new head
    self.snake.appendleft((new_row, new_col))
    self.occupied_positions.add((new_row, new_col))

2. Not Synchronizing Snake Body and Position Set

The Pitfall: Forgetting to update the occupied_positions set when modifying the snake deque leads to inconsistent state.

Common Mistakes:

• Adding to deque but not to set
• Removing from deque but not from set
• Using list operations that bypass the set updates

Prevention: Always pair deque and set operations:

# Always together for adding
self.snake.appendleft(new_pos)
self.occupied_positions.add(new_pos)

# Always together for removing
removed = self.snake.pop()
self.occupied_positions.remove(removed)

3. Misunderstanding Food Index Bounds

The Pitfall: Not properly checking if all food has been consumed before accessing self.food[self.food_index].

Incorrect:

# This will cause IndexError when food_index >= len(food)
if (new_row == self.food[self.food_index][0] and
    new_col == self.food[self.food_index][1]):

Correct:

if (self.food_index < len(self.food) and
    new_row == self.food[self.food_index][0] and
    new_col == self.food[self.food_index][1]):

The short-circuit evaluation ensures we don't access an invalid index when all food is consumed.