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.
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 ; } }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.