# Snake in Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/snake-in-matrix)
Canonical: https://scaleengineer.com/dsa/problems/snake-in-matrix
**Data structures:** Array, String
---
## Problem
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 <= 10`
* `1 <= commands.length <= 100`
* `commands` consists only of `"UP"`, `"RIGHT"`, `"DOWN"`, and `"LEFT"`.
* The input is generated such the snake will not move outside of the boundaries.

# Approaches
## Grid-Based Simulation
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.
**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.
**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.
### Explanation
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]`. 

```java
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];
    }
}
```
### Algorithm
*   Initialize an `n x n` integer matrix, `grid`.
*   Use nested loops to populate the `grid`: for each cell `(i, j)`, set `grid[i][j] = i * n + j`.
*   Initialize the snake's coordinates: `int row = 0;`, `int col = 0;`.
*   Iterate through the `commands` array.
*   For each `command`, update the `row` and `col` variables.
*   After the loop finishes, the final coordinates are `(row, col)`.
*   The result is the value at `grid[row][col]`.

## Direct Coordinate Simulation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Initialize the snake's coordinates: `int row = 0;`, `int col = 0;`.
*   Iterate through the `commands` array.
*   For each `command`, update the `row` and `col` variables based on the direction.
*   After iterating through all commands, calculate the final cell position using the formula: `finalPosition = row * n + col`.
*   Return `finalPosition`.

# Solutions
### Java

```java
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 ; } }

```

### Python

```python
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 + y

```

### CPP

```cpp
class 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;
  }
};

```