LeetCode 353: Design Snake Game Solution

Master LeetCode problem 353 (Design Snake Game), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

353. Design Snake Game

Medium

Array Hash Table Design Queue Simulation

Problem Explanation

Explanation

To design the Snake Game, we can use a deque to represent the snake's body. We will also maintain a set to track the positions occupied by the snake. To move the snake, we will add the new head position to the deque and set. If the new head position is valid, we will update the snake's position accordingly. If the new head position is invalid (e.g., hitting the wall or eating itself), the game ends. We will also keep track of the current score based on the food eaten by the snake.

Algorithm Steps:

Initialize the snake's initial position, direction, and set of occupied positions.
When moving the snake:
- Calculate the new head position based on the current direction.
- Check if the new head position is valid (within boundaries and not hitting itself).
- If the new head position is food, increment the score, increase the snake's length, and place a new food randomly.
- Update the snake's position by adding the new head and removing the tail if not eating food.
Repeat the process until the game ends.

Time Complexity

Moving the snake and checking for collisions: O(1)
Placing a new food: O(n) where n is the number of empty cells

Space Complexity

O(n) where n is the size of the grid

Solution Code

class SnakeGame {
    int width, height, score, foodIndex;
    int[][] food;
    Deque<int[]> snake;
    Set<Integer> occupied;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.snake = new LinkedList<>();
        this.snake.add(new int[]{0, 0});
        this.occupied = new HashSet<>();
        this.occupied.add(0);
        this.score = 0;
        this.foodIndex = 0;
    }

    public int move(String direction) {
        int[] head = snake.getFirst();
        int[] next = new int[]{head[0], head[1]};
        switch (direction) {
            case "U": next[0]--; break;
            case "D": next[0]++; break;
            case "L": next[1]--; break;
            case "R": next[1]++; break;
        }

        int headIndex = next[0] * width + next[1];
        boolean valid = next[0] >= 0 && next[0] < height && next[1] >= 0 && next[1] < width &&
                (snake.size() == 1 || (headIndex != snake.getLast()[0] * width + snake.getLast()[1])) &&
                !occupied.contains(headIndex);

        if (!valid) return -1;

        snake.addFirst(next);
        occupied.add(headIndex);

        if (foodIndex < food.length && next[0] == food[foodIndex][0] && next[1] == food[foodIndex][1]) {
            score++;
            foodIndex++;
        } else {
            int[] tail = snake.removeLast();
            occupied.remove(tail[0] * width + tail[1]);
        }

        return score;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 353 (Design Snake Game)?

This page provides optimized solutions for LeetCode problem 353 (Design Snake Game) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 353 (Design Snake Game)?

The time complexity for LeetCode 353 (Design Snake Game) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 353 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 353 in Java, C++, or Python.

Back to LeetCode Solutions