Snake in Matrix
EasyPrompt
There is a snake in an n x n matrix grid and can move in four possible directions. Each cell in the grid is identified by the position: grid[i][j] = (i * n) + j.
The snake starts at cell 0 and follows a sequence of commands.
You are given an integer n representing the size of the grid and an array of strings commands where each command[i] is either "UP", "RIGHT", "DOWN", and "LEFT". It's guaranteed that the snake will remain within the grid boundaries throughout its movement.
Return the position of the final cell where the snake ends up after executing commands.
Example 1:
Input: n = 2, commands = ["RIGHT","DOWN"]
Output: 3
Explanation:
| 0 | 1 |
| 2 | 3 |
| 0 | 1 |
| 2 | 3 |
| 0 | 1 |
| 2 | 3 |
Example 2:
Input: n = 3, commands = ["DOWN","RIGHT","UP"]
Output: 1
Explanation:
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
Constraints:
2 <= n <= 101 <= commands.length <= 100commandsconsists only of"UP","RIGHT","DOWN", and"LEFT".- The input is generated such the snake will not move outside of the boundaries.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves creating an explicit n x n matrix in memory to represent the grid. We first populate this matrix with the corresponding cell numbers. Then, we simulate the snake's movement by tracking its row and column indices. After all commands are executed, we look up the final cell number from our matrix using the final row and column.
Algorithm
- Initialize an
n x ninteger matrix,grid. - Use nested loops to populate the
grid: for each cell(i, j), setgrid[i][j] = i * n + j. - Initialize the snake's coordinates:
int row = 0;,int col = 0;. - Iterate through the
commandsarray. - For each
command, update therowandcolvariables. - After the loop finishes, the final coordinates are
(row, col). - The result is the value at
grid[row][col].
Walkthrough
We start by initializing an n x n integer matrix. This matrix is then filled with cell numbers according to the formula grid[i][j] = i * n + j. The snake's position is tracked using row and col variables, initialized to 0. We then loop through each command, updating the row and col based on the direction. For example, an "UP" command decrements the row. Since the problem guarantees the snake stays within bounds, no boundary checks are needed. Finally, after processing all commands, the result is simply the value stored at grid[row][col].
class Solution { public int snakeInMatrix(int n, String[] commands) { int[][] grid = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { grid[i][j] = i * n + j; } } int row = 0; int col = 0; for (String command : commands) { if (command.equals("UP")) { row--; } else if (command.equals("DOWN")) { row++; } else if (command.equals("LEFT")) { col--; } else if (command.equals("RIGHT")) { col++; } } return grid[row][col]; }}Complexity
Time
`O(n^2 + C)`, where `n` is the size of the grid and `C` is the number of commands. The `O(n^2)` term comes from initializing the grid, and `O(C)` comes from processing the commands.
Space
`O(n^2)` to store the `n x n` grid in memory.
Trade-offs
Pros
Conceptually simple and easy to visualize, as it directly models the problem statement's grid.
The logic for finding the final value is a direct lookup, which is intuitive.
Cons
Inefficient in terms of space, as it requires
O(n^2)memory to store the grid.Slightly less efficient in time due to the initial
O(n^2)step to populate the grid.
This is a more optimized approach that avoids creating the grid in memory. We only need to keep track of the snake's current row and column. We start at (0, 0) and update these coordinates for each command. Once all commands are processed, we use the final coordinates and the given formula (row * n) + col to calculate the final cell number directly.
Algorithm
- Initialize the snake's coordinates:
int row = 0;,int col = 0;. - Iterate through the
commandsarray. - For each
command, update therowandcolvariables based on the direction. - After iterating through all commands, calculate the final cell position using the formula:
finalPosition = row * n + col. - Return
finalPosition.
Walkthrough
This method directly simulates the snake's movement by tracking its (row, col) coordinates without building the grid. We initialize row = 0 and col = 0, corresponding to the starting cell 0. We then iterate through the list of commands. A switch statement is an efficient way to handle the different command strings. For each command, we adjust row or col accordingly. For instance, "RIGHT" increments col. After the loop completes, we have the final (row, col) coordinates. The final cell number is then computed using the provided formula row * n + col and returned.
class Solution { public int snakeInMatrix(int n, String[] commands) { int row = 0; int col = 0; for (String command : commands) { switch (command) { case "UP": row--; break; case "DOWN": row++; break; case "LEFT": col--; break; case "RIGHT": col++; break; } } return row * n + col; }}Complexity
Time
`O(C)`, where `C` is the number of commands. We simply iterate through the commands once.
Space
`O(1)`. We only use a few variables to store the current position, regardless of the size of the grid or the number of commands.
Trade-offs
Pros
Highly efficient in both time and space.
Avoids the overhead of creating and populating a large data structure.
The logic is clean and directly solves the problem without unnecessary steps.
Cons
Requires understanding the mapping between the 1D cell number and the 2D grid coordinates, which might be slightly less intuitive than having an explicit grid.
Solutions
Solution
class Solution {public int finalPositionOfSnake(int n, List<String> commands) { int x = 0, y = 0; for (var c : commands) { switch (c.charAt(0)) { case 'U' -> x --; case 'D' -> x ++; case 'L' -> y --; case 'R' -> y ++; } } return x * n + y ; } }class Solution: def finalPositionOfSnake(self, n: int, commands: List[str]) -> int: x = y = 0 for c in commands: match c[0]: case "U": x -= 1 case "D": x += 1 case "L": y -= 1 case "R": y += 1 return x * n + yclass Solution {public: int finalPositionOfSnake(int n, vector<string> &commands) { int x = 0, y = 0; for (const auto &c : commands) { switch (c[0]) { case 'U': x--; break; case 'D': x++; break; case 'L': y--; break; case 'R': y++; break; } } return x * n + y; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.