How hard is LeetCode 353. Design Snake Game?

LeetCode 353. Design Snake Game is rated Medium on LeetCode.

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

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 353. Design Snake Game?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 353. Design Snake Game cover?

LeetCode 353. Design Snake Game is tagged Design, Queue, Array, Hash Table and Simulation on LeetCode.

Is LeetCode 353. Design Snake Game a premium problem?

Yes. LeetCode 353. Design Snake Game is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Design Snake Game — LeetCode 353 Python Solution

MediumLeetCode PremiumDesignQueueArrayHash TableSimulation

Problem: #353
Pattern: Stack
Reading time: 8 min
Source: leetcode.com

The problem

Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.

Example

Input: ["SnakeGame", "move", "move", "move", "move", "move", "move"]
Output: [null, 0, 0, 1, 1, 2, -1]
Explanation: SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);

Python solution

Python

class SnakeGame:
    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.m = height
        self.n = width
        self.food = food
        self.score = 0
        self.idx = 0
        self.q = deque([(0, 0)])
        self.vis = {(0, 0)}

    def move(self, direction: str) -> int:
        i, j = self.q[0]
        x, y = i, j
        match direction:
            case "U":
                x -= 1
            case "D":
                x += 1
            case "L":
                y -= 1
            case "R":
                y += 1
        if x < 0 or x >= self.m or y < 0 or y >= self.n:
            return -1
        if (
            self.idx < len(self.food)
            and x == self.food[self.idx][0]
            and y == self.food[self.idx][1]
        ):
            self.score += 1
            self.idx += 1
        else:
            self.vis.remove(self.q.pop())
        if (x, y) in self.vis:
            return -1
        self.q.appendleft((x, y))
        self.vis.add((x, y))
        return self.score


# Your SnakeGame object will be instantiated and called as such:
# obj = SnakeGame(width, height, food)
# param_1 = obj.move(direction)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 353. Design Snake Game is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 353. Design Snake Game?: LeetCode 353. Design Snake Game is rated Medium on LeetCode.
What is the time complexity of LeetCode 353. Design Snake Game?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 353. Design Snake Game?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 353. Design Snake Game cover?: LeetCode 353. Design Snake Game is tagged Design, Queue, Array, Hash Table and Simulation on LeetCode.
Is LeetCode 353. Design Snake Game a premium problem?: Yes. LeetCode 353. Design Snake Game is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.