Design Snake Game - Practice Coding Problems

Design Snake Game - Problem

Design a Snake game that is played on a device with screen size height x width. The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food. When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

Input & Output

Example 1 — Basic Snake Movement

$ Input: SnakeGame(3, 2, [[1,2],[0,1]]), move("R"), move("D"), move("R")

› Output: [null, 0, 0, 1]

💡 Note: Initialize 3×2 board with food at (1,2) and (0,1). Move right to (0,1): no food, score=0. Move down to (1,1): no food, score=0. Move right to (1,2): eat food, score=1.

Example 2 — Hit Boundary

$ Input: SnakeGame(3, 2, []), move("L")

› Output: [null, -1]

💡 Note: Snake starts at (0,0). Move left would go to (0,-1) which is out of bounds, so return -1.

Example 3 — Self Collision

$ Input: SnakeGame(2, 2, [[0,1],[1,1],[1,0]]), move("R"), move("D"), move("L"), move("U")

› Output: [null, 1, 2, 3, -1]

💡 Note: Snake grows by eating food at (0,1), (1,1), (1,0). Final move up would hit its own body at (0,0), causing game over.

Constraints

1 ≤ width, height ≤ 10⁴
1 ≤ food.length ≤ 50
food[i].length == 2
0 ≤ ri < height
0 ≤ ci < width
direction is 'U', 'D', 'L', or 'R'
At most 10⁴ calls will be made to move

Visualization

Tap to expand

Understanding the Visualization

Initial Setup

Snake at (0,0) on width×height board with food positions

Movement

Snake moves in direction, checks bounds and self-collision

Game Logic

Handle food consumption, growth, and score updates

Key Takeaway

🎯 Key Insight: Combine queue for body order with hash set for instant collision detection

Asked in

G Google 28 a Amazon 22 M Microsoft 15 🍎 Apple 12

The key insight is to use a queue to maintain snake body order and a hash set for O(1) collision detection. The optimal approach combines these data structures for efficient movement processing. Time: O(1) per move, Space: O(n) where n is snake length.

Common Approaches

Approach	Time	Space	Notes
✓ Queue + Hash Set	O(1)	O(n)	Use queue for body order and hash set for O(1) collision detection
Brute Force with Array	O(n)	O(n)	Store snake body in array and check all positions for collisions

Queue + Hash Set — Algorithm Steps

Use queue to store snake body positions
Use hash set for O(1) collision lookup
Move head and check bounds/collision instantly
Update queue and set based on food consumption

Visualization

Tap to expand

Step-by-Step Walkthrough

Data Structures

Queue maintains order, Set enables O(1) lookup

Move Operation

Instant collision check using hash set

Update

Efficiently update both structures

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

typedef struct {
    int row, col;
} Position;

typedef struct {
    int width, height;
    Position *food;
    int foodSize;
    int foodIndex;
    int score;
    Position snake[MAX_SIZE];
    int snakeSize;
    char positionSet[MAX_SIZE][20];  // Simple hash set simulation
    int setSize;
} SnakeGame;

int findInSet(SnakeGame* obj, int row, int col) {
    char key[20];
    sprintf(key, "%d,%d", row, col);
    for (int i = 0; i < obj->setSize; i++) {
        if (strcmp(obj->positionSet[i], key) == 0) {
            return i;
        }
    }
    return -1;
}

void addToSet(SnakeGame* obj, int row, int col) {
    sprintf(obj->positionSet[obj->setSize], "%d,%d", row, col);
    obj->setSize++;
}

void removeFromSet(SnakeGame* obj, int row, int col) {
    int index = findInSet(obj, row, col);
    if (index != -1) {
        for (int i = index; i < obj->setSize - 1; i++) {
            strcpy(obj->positionSet[i], obj->positionSet[i + 1]);
        }
        obj->setSize--;
    }
}

SnakeGame* snakeGameCreate(int width, int height, Position* food, int foodSize) {
    SnakeGame* obj = (SnakeGame*)malloc(sizeof(SnakeGame));
    obj->width = width;
    obj->height = height;
    obj->food = food;
    obj->foodSize = foodSize;
    obj->foodIndex = 0;
    obj->score = 0;
    obj->snake[0].row = 0;
    obj->snake[0].col = 0;
    obj->snakeSize = 1;
    obj->setSize = 0;
    addToSet(obj, 0, 0);
    return obj;
}

int snakeGameMove(SnakeGame* obj, char* direction) {
    Position head = obj->snake[0];
    Position newHead;
    
    if (strcmp(direction, "U") == 0) {
        newHead.row = head.row - 1;
        newHead.col = head.col;
    } else if (strcmp(direction, "D") == 0) {
        newHead.row = head.row + 1;
        newHead.col = head.col;
    } else if (strcmp(direction, "L") == 0) {
        newHead.row = head.row;
        newHead.col = head.col - 1;
    } else {
        newHead.row = head.row;
        newHead.col = head.col + 1;
    }
    
    if (newHead.row < 0 || newHead.row >= obj->height ||
        newHead.col < 0 || newHead.col >= obj->width) {
        return -1;
    }
    
    int ateFood = (obj->foodIndex < obj->foodSize &&
                   newHead.row == obj->food[obj->foodIndex].row &&
                   newHead.col == obj->food[obj->foodIndex].col);
    
    if (!ateFood) {
        Position tail = obj->snake[obj->snakeSize - 1];
        obj->snakeSize--;
        removeFromSet(obj, tail.row, tail.col);
    }
    
    if (findInSet(obj, newHead.row, newHead.col) != -1) {
        return -1;
    }
    
    for (int i = obj->snakeSize; i > 0; i--) {
        obj->snake[i] = obj->snake[i - 1];
    }
    obj->snake[0] = newHead;
    obj->snakeSize++;
    addToSet(obj, newHead.row, newHead.col);
    
    if (ateFood) {
        obj->score++;
        obj->foodIndex++;
    }
    
    return obj->score;
}

int main() {
    printf("[null,0,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Each move operation involves constant time queue and hash set operations

✓ Linear Growth

Space Complexity

O(n)

Queue and hash set both store n positions where n is snake length

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Queue + Hash Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler