LeetCode 3248 - Snake in Matrix

LeetCode Problem 3248

Difficulty: 🟢 Easy
Topics: Array, String, Simulation

Solution

Problem Understanding

The problem describes a snake moving inside an n x n grid. Every cell in the grid is assigned a numeric position using the formula:

$$\text{grid}[i][j] = (i \times n) + j$$

This means the grid is numbered row by row, starting from the top-left corner.

For example, when n = 3, the grid looks like this:

Row	Values
0	0 1 2
1	3 4 5
2	6 7 8

The snake always starts at position 0, which corresponds to the top-left corner (0, 0).

You are given a sequence of movement commands. Each command tells the snake to move one cell in one of four directions:

• "UP"
• "DOWN"
• "LEFT"
• "RIGHT"

The task is to determine the numeric position of the snake after executing all commands.

The constraints are very small:

• n is at most 10
• There are at most 100 commands

This tells us the input size is tiny, so performance is not a concern. Even a straightforward simulation will easily fit within limits.

An important guarantee is that the snake never moves outside the grid boundaries. This means we do not need to write boundary-checking logic. Every move is always valid.

Some important edge cases include:

• A command sequence that moves back and forth repeatedly.
• Movement only in one direction.
• Smallest grid size, n = 2.
• Returning back to the starting cell after several moves.
• Multiple vertical moves, because vertical movement changes the position by n, not by 1.

A naive implementation can easily make mistakes when converting between row-column coordinates and the flattened cell index, especially for vertical movement.

Approaches

Brute Force Approach

The most direct solution is to explicitly track the snake's row and column coordinates.

We start with:

• row = 0
• col = 0

For each command:

• "UP" decreases the row.
• "DOWN" increases the row.
• "LEFT" decreases the column.
• "RIGHT" increases the column.

After processing all commands, we convert the final (row, col) position back into the cell number using:

$$\text{position} = (row \times n) + col$$

This approach is correct because every command directly corresponds to a movement inside the matrix.

Although this solution is already efficient enough for the given constraints, it still performs unnecessary coordinate conversions.

Optimal Approach

The key observation is that we do not actually need to maintain row and column separately.

Because the grid numbering follows:

$$\text{grid}[i][j] = (i \times n) + j$$

we can directly update the numeric position itself.

Moving:

• "RIGHT" increases position by 1
• "LEFT" decreases position by 1
• "DOWN" increases position by n
• "UP" decreases position by n

This works because horizontal movement changes the column index by one, while vertical movement changes the row index by one entire row of length n.

Instead of converting coordinates repeatedly, we directly simulate movement on the flattened index.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m)	O(1)	Tracks row and column separately
Optimal	O(m)	O(1)	Directly updates flattened position index

Here, m is the number of commands.

Algorithm Walkthrough

1. Initialize a variable position = 0.

The snake always starts at cell 0, so this variable represents the current location. 2. Iterate through every command in commands.

Each command represents one movement step. 3. For each command, update the position accordingly.

• If the command is "RIGHT", add 1.
• If the command is "LEFT", subtract 1.
• If the command is "DOWN", add n.
• If the command is "UP", subtract n.

These updates directly match how cells are numbered in the matrix. 4. After processing all commands, return position.

This value already represents the final flattened cell index.

Why it works

The numbering system assigns consecutive numbers across rows. Horizontal movement changes the index by exactly 1, while vertical movement skips an entire row of length n. Since every command corresponds exactly to one of these transformations, repeatedly applying these updates always produces the correct final cell index.

Python Solution

from typing import List

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        position = 0

        for command in commands:
            if command == "RIGHT":
                position += 1
            elif command == "LEFT":
                position -= 1
            elif command == "DOWN":
                position += n
            else:  # "UP"
                position -= n

        return position

The implementation begins by initializing position to 0, because the snake always starts at the top-left cell.

The loop processes each movement command one at a time. Instead of maintaining row and column coordinates separately, the code directly modifies the flattened index.

Horizontal movements adjust the index by 1, while vertical movements adjust it by n, which corresponds to moving an entire row up or down.

Finally, the method returns the computed position after all commands have been executed.

Go Solution

func finalPositionOfSnake(n int, commands []string) int {
    position := 0

    for _, command := range commands {
        if command == "RIGHT" {
            position += 1
        } else if command == "LEFT" {
            position -= 1
        } else if command == "DOWN" {
            position += n
        } else { // "UP"
            position -= n
        }
    }

    return position
}

The Go implementation follows exactly the same logic as the Python version.

Go uses a for _, command := range commands loop to iterate through the slice of commands. String comparisons are performed directly using ==.

No special handling is required for empty slices because the constraints guarantee at least one command. Integer overflow is also not a concern because the grid size and number of commands are extremely small.

Worked Examples

Example 1

Input:

n = 2
commands = ["RIGHT", "DOWN"]

Grid:

0	1
2	3

Initial position:

position = 0

Process commands:

Command	Calculation	New Position
RIGHT	0 + 1	1
DOWN	1 + 2	3

Final answer:

3

Example 2

Input:

n = 3
commands = ["DOWN", "RIGHT", "UP"]

Grid:

0	1	2
3	4	5
6	7	8

Initial position:

position = 0

Process commands:

Command	Calculation	New Position
DOWN	0 + 3	3
RIGHT	3 + 1	4
UP	4 - 3	1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m)	Each command is processed once
Space	O(1)	Only a single position variable is used

The algorithm performs one constant-time update for every command. No additional data structures are allocated, so the memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        position = 0

        for command in commands:
            if command == "RIGHT":
                position += 1
            elif command == "LEFT":
                position -= 1
            elif command == "DOWN":
                position += n
            else:
                position -= n

        return position

sol = Solution()

assert sol.finalPositionOfSnake(2, ["RIGHT", "DOWN"]) == 3  # provided example 1
assert sol.finalPositionOfSnake(3, ["DOWN", "RIGHT", "UP"]) == 1  # provided example 2

assert sol.finalPositionOfSnake(2, ["DOWN"]) == 2  # single vertical move
assert sol.finalPositionOfSnake(2, ["RIGHT"]) == 1  # single horizontal move

assert sol.finalPositionOfSnake(3, ["RIGHT", "LEFT"]) == 0  # returns to start
assert sol.finalPositionOfSnake(4, ["DOWN", "DOWN"]) == 8  # multiple row jumps

assert sol.finalPositionOfSnake(5, ["RIGHT", "RIGHT", "DOWN"]) == 7  # mixed movement
assert sol.finalPositionOfSnake(5, ["DOWN", "RIGHT", "RIGHT", "UP", "LEFT"]) == 1  # complex path

assert sol.finalPositionOfSnake(10, ["DOWN"] * 9) == 90  # maximum vertical traversal
assert sol.finalPositionOfSnake(10, ["RIGHT"] * 9) == 9  # maximum horizontal traversal

Test	Why
n=2, ["RIGHT","DOWN"]	Validates provided example
n=3, ["DOWN","RIGHT","UP"]	Validates mixed movement
n=2, ["DOWN"]	Tests vertical movement
n=2, ["RIGHT"]	Tests horizontal movement
["RIGHT","LEFT"]	Ensures reverse movement works
["DOWN","DOWN"]	Tests repeated row transitions
Mixed movement path	Verifies combined operations
Return near start	Ensures correct incremental updates
Maximum downward moves	Tests large vertical offsets
Maximum rightward moves	Tests edge horizontal traversal

Edge Cases

One important edge case is movement that immediately reverses direction, such as "RIGHT" followed by "LEFT". A buggy implementation might incorrectly accumulate movement or mishandle index updates. The solution handles this naturally because each command directly modifies the current position, and opposite operations cancel each other out correctly.

Another important case is repeated vertical movement. Since vertical movement changes the flattened index by n rather than 1, implementations that confuse row movement with column movement can produce incorrect answers. This implementation explicitly adds or subtracts n for "DOWN" and "UP", ensuring accurate row transitions.

A third edge case involves returning to the starting position after several moves. For example, a sequence like ["DOWN", "UP"] should end at 0. Because the algorithm maintains a running position total and applies inverse operations correctly, it naturally handles these cases without special logic.

Finally, very small grids such as n = 2 can expose off-by-one mistakes in coordinate calculations. Since this implementation avoids explicit coordinate conversion entirely and directly updates the flattened index, it avoids many common indexing bugs.