Prerequisites

Before attempting this problem, you should be comfortable with:

  • Deque (Double-Ended Queue) - Adding to front and removing from back in O(1) time
  • Hash Set - O(1) lookup for collision detection
  • 2D Coordinate Systems - Working with row/column positions and boundary checking

1. Queue and Hash Set

Intuition

The snake game requires tracking the snake's body as it moves and grows. A deque (double-ended queue) is perfect because we add to the front (new head position) and remove from the back (tail moves forward). To quickly check whether the snake bites itself, we also maintain a hash set of all occupied cells. When the snake eats food, the tail stays in place so the snake grows. The score equals the number of food items eaten, which is the snake length minus 1.

Algorithm

  1. Initialization: Create a deque with the snake starting at (0, 0). Add this position to a hash set. Store the grid dimensions, food list, and a food index starting at 0. Define movement deltas for U, D, L, R.
  2. move(direction): Calculate the new head position by applying the direction delta.
  3. Check if the new head is out of bounds. If so, return -1.
  4. Check if the new head collides with the snake body (exists in the hash set and is not the current tail). If so, return -1.
  5. If there is food at the new head position, increment the food index (the tail stays, so the snake grows).
  6. Otherwise, remove the tail from the deque and the hash set (the snake moves without growing).
  7. Add the new head to the front of the deque and to the hash set.
  8. Return the current score (snake length minus 1).
class SnakeGame:

    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.snake = collections.deque([(0,0)])    # snake head is at the front
        self.snake_set = {(0,0) : 1}
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0
        self.movement = {'U': [-1, 0], 'L': [0, -1], 'R': [0, 1], 'D': [1, 0]}
        

    def move(self, direction: str) -> int:
        newHead = (self.snake[0][0] + self.movement[direction][0],
                   self.snake[0][1] + self.movement[direction][1])
        
        # Boundary conditions.
        crosses_boundary1 = newHead[0] < 0 or newHead[0] >= self.height
        crosses_boundary2 = newHead[1] < 0 or newHead[1] >= self.width
        
        # Checking if the snake bites itself.
        bites_itself = newHead in self.snake_set and newHead != self.snake[-1]
     
        # If any of the terminal conditions are satisfied, then we exit with rcode -1.
        if crosses_boundary1 or crosses_boundary2 or bites_itself:
            return -1

        # Note the food list could be empty at this point.
        next_food_item = self.food[self.food_index] if self.food_index < len(self.food) else None
        
        # If there's an available food item and it is on the cell occupied by the snake after the move, eat it
        if self.food_index < len(self.food) and \
            next_food_item[0] == newHead[0] and \
                next_food_item[1] == newHead[1]:  # eat food
            self.food_index += 1
        else:    # not eating food: delete tail                 
            tail = self.snake.pop()  
            del self.snake_set[tail]
            
        # A new head always gets added
        self.snake.appendleft(newHead)
        
        # Also add the head to the set
        self.snake_set[newHead] = 1

        return len(self.snake) - 1

Time & Space Complexity

  • Time Complexity:

    • The time complexity of the move function is O(1)O(1).
    • The time taken to calculate bites_itself is constant since we are using a dictionary to search for the element.
    • The time taken to add and remove an element from the queue is also constant.

  • Space Complexity: O(W×H+N)O(W \times H + N)

    • O(N)O(N) is used by the food data structure.
    • O(W×H)O(W \times H) is used by the snake and the snake_set data structures. At most, we can have snake that occupies all the cells of the grid.

Where WW represents the width of the grid, HH represents the height of the grid, and NN represents the number of food items in the list.

Common Pitfalls

Confusing Width and Height with Row and Column

The grid is defined as width x height, but positions are given as [row, col] where row corresponds to height and column corresponds to width. Mixing these up causes incorrect boundary checks.

# Wrong: swapped width/height in boundary check
crosses_boundary1 = newHead[0] < 0 or newHead[0] >= self.width   # Should be height
crosses_boundary2 = newHead[1] < 0 or newHead[1] >= self.height  # Should be width

# Correct
crosses_boundary1 = newHead[0] < 0 or newHead[0] >= self.height  # row vs height
crosses_boundary2 = newHead[1] < 0 or newHead[1] >= self.width   # col vs width

Not Excluding Tail When Checking Self-Collision

When the snake moves without eating, the tail vacates its position. The new head can legally occupy the old tail position. Failing to exclude the tail from collision detection causes false game-overs.

# Wrong: doesn't account for tail moving
bites_itself = newHead in self.snake_set

# Correct: tail position will be vacated (unless eating)
bites_itself = newHead in self.snake_set and newHead != self.snake[-1]

Wrong Order of Operations When Eating Food

When eating food, you must not remove the tail (so the snake grows). When not eating, you must remove the tail before adding the new head. Getting this order wrong causes the snake to grow incorrectly or the set to become inconsistent.

# Wrong: always removes tail, then checks food
tail = self.snake.pop()
del self.snake_set[tail]
if is_food:
    # Too late - tail already removed!
    pass

# Correct: check food first, only remove tail if not eating
if is_food:
    self.food_index += 1
else:
    tail = self.snake.pop()
    del self.snake_set[tail]
self.snake.appendleft(newHead)
self.snake_set[newHead] = 1