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.

Example 1

Input

Output

Explanation

Constraints

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

Real World Applications 🌎

We all crushed the snake game on those Nokias, right? Thinking about how this is implemented under the hood is a nice closure for those simpler days. Let’s reminisce for a moment.

The Finer Details 🔎

This question can seem daunting at first because there is a lot of business logic we need to implement. What I like to do in questions like these is mock the functions I wish I had. Once I have clarity on the functionality that I’d like our class to support we can focus on implementing each one individually. This already saves us from writing spaghetti code and helps us break down the problem further.

So, which util methods did we wish existed?

I’d love the following:

incrementSnakePosition -> takes care of incrementing the snake position on the board

isCoordInvalid -> will tell us if the new coordinate is valid. It can be invalid if a user crashes into the game borders or the snake crashes into itself.

foundFood -> A method that takes care of the case when a user has successfully hit a food cell.

Solution 💡

Complexity Analysis 🧮

Time Complexity

O(1)

All methods require a constant amount of operations.

Space Complexity

O(HxW + N)

Explanation

O(HxW) -> If a user wins the game, they can occupy the whole board!

O(N) -> We receive N food coordinates for the snake

Takeaways 🎉🥳

• Developing the ability to break down problems like this highlights systematic thinking and is a great signal for your interviewer.
• When facing a problem with many “mini-tasks” take a step back. Think about the primitives you wish existed that would help you solve this easily.
• If you write spaghetti code initially, think about refactoring when reviewing your code. It will help you test your code and reason about logic.

Resources 📚

Leetcode