Snake in Matrix - Practice Coding Problems

Snake in Matrix - Problem

There is a snake in an n x n matrix grid that 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 commands[i] is either "UP", "RIGHT", "DOWN", or "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 all commands.

Input & Output

Example 1 — Basic Movement

$ Input: n = 2, commands = ["RIGHT", "DOWN"]

› Output: 3

💡 Note: Start at position 0 (row=0, col=0). Move RIGHT to (0,1). Move DOWN to (1,1). Final position = 1*2 + 1 = 3

Example 2 — Single Move

$ Input: n = 3, commands = ["DOWN", "RIGHT", "UP"]

› Output: 1

💡 Note: Start at (0,0). DOWN to (1,0). RIGHT to (1,1). UP to (0,1). Final position = 0*3 + 1 = 1

Example 3 — Return to Start

$ Input: n = 2, commands = ["RIGHT", "LEFT"]

› Output: 0

💡 Note: Start at (0,0). RIGHT to (0,1). LEFT back to (0,0). Final position = 0*2 + 0 = 0

Constraints

1 ≤ n ≤ 10³
1 ≤ commands.length ≤ 10⁴
commands[i] is either "UP", "RIGHT", "DOWN", or "LEFT"
The snake will remain within the grid boundaries

Visualization

Tap to expand

Understanding the Visualization

Input

Grid size n=3, commands=["RIGHT","DOWN","LEFT"]

Process

Snake follows commands starting from position 0

Output

Final position where snake ends up

Key Takeaway

🎯 Key Insight: Track coordinates directly instead of converting position repeatedly

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to convert between 1D position and 2D coordinates using division and modulo. Best approach is to track row/col directly throughout movement. Time: O(m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Position Tracking	O(m)	O(1)	Track current position and convert to coordinates for each move
Coordinate Tracking	O(m)	O(1)	Track row and column separately throughout the movement

Direct Position Tracking — Algorithm Steps

Start at position 0
For each command, convert position to (row, col)
Apply move direction
Convert back to position

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Position 0 in 3×3 grid

Move Right

Convert 0 → (0,0), move right → (0,1), convert → position 1

Result

Final position after all moves

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n, char commands[][10], int commandsSize) {
    int position = 0;
    
    for (int i = 0; i < commandsSize; i++) {
        // Convert position to coordinates
        int row = position / n;
        int col = position % n;
        
        // Apply move
        if (strcmp(commands[i], "UP") == 0) {
            row -= 1;
        } else if (strcmp(commands[i], "DOWN") == 0) {
            row += 1;
        } else if (strcmp(commands[i], "LEFT") == 0) {
            col -= 1;
        } else if (strcmp(commands[i], "RIGHT") == 0) {
            col += 1;
        }
        
        // Convert back to position
        position = row * n + col;
    }
    
    return position;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    char commands[100][10];
    int commandsSize = 0;
    
    char *token = strtok(line, "[],\"");
    while (token != NULL && commandsSize < 100) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(commands[commandsSize], token);
            commandsSize++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    printf("%d\n", solution(n, commands, commandsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m)

Process each of m commands once

✓ Linear Growth

Space Complexity

O(1)

Only store current position and temporary coordinates

✓ Linear Space

12.0K Views

Medium Frequency

~8 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Position Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler