3248. Snake in Matrix

EasyArrayStringSimulation

Problem Description

You are given a n x n grid where each cell is identified by its position: grid[i][j] = (i * n) + j. There is a snake that starts at the top-left corner of this grid, cell 0, and it can move in four possible directions: "UP", "RIGHT", "DOWN", and "LEFT". You are given an integer n representing the size of the grid, and an array of strings commands, where each command corresponds to a direction that the snake must move. The movements are guaranteed to keep the snake within the boundaries of the grid. Your task is to determine the position in the grid (in a specific index format) where the snake ends after executing all the commands.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The solution to this problem revolves around simulating the movements of the snake across the grid based on the given commands. Initially, the position of the snake is (0, 0), which corresponds to the top-left corner of the grid.

As we process each command in the commands list:

"UP" decreases the row index x by 1.
"DOWN" increases the row index x by 1.
"LEFT" decreases the column index y by 1.
"RIGHT" increases the column index y by 1.

Using these simple updates, we modify the current position of the snake in terms of x (row) and y (column). At the end of processing all the commands, we calculate the final position index using the formula x * n + y, which converts the 2D grid position into a single index as required by the problem. This approach is straightforward and efficient since it directly simulates the movement while taking advantage of the problem's constraints that keep the snake within the grid.

Solution Approach

To implement the solution, we utilize a simulation approach which can be divided into the following steps:

Initialize Position: Start the snake at the initial position (x, y) = (0, 0), which represents the top-left corner of the grid.
Iterate Through Commands: Use a loop to iterate through each command in the commands list. Depending on the direction specified by each command, we update the snake's position:
- If the current command is "UP", decrement x by 1 (x -= 1).
- If the current command is "DOWN", increment x by 1 (x += 1).
- If the current command is "LEFT", decrement y by 1 (y -= 1).
- If the current command is "RIGHT", increment y by 1 (y += 1).
Final Calculation: After processing all commands, compute the snake's final position in terms of a single index. The 2D to 1D position conversion is accomplished by the formula x * n + y.
Return Result: Return the computed final index as the result.

The following code snippet demonstrates this method in Python:

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        x = y = 0
        for c in commands:
            if c[0] == "U":  # "UP"
                x -= 1
            elif c[0] == "D":  # "DOWN"
                x += 1
            elif c[0] == "L":  # "LEFT"
                y -= 1
            elif c[0] == "R":  # "RIGHT"
                y += 1
        return x * n + y

This code efficiently computes the final position of the snake, relying on basic arithmetic operations and the appropriate handling of each movement direction.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Suppose n = 3, meaning we have a 3x3 grid, and the commands array is ["RIGHT", "DOWN", "DOWN", "LEFT"].

Initialize Position: Start at position (x, y) = (0, 0), which corresponds to cell 0 in a 1D index.
Process Commands:
- Command "RIGHT": Move right from (0, 0) to (0, 1). The column index y increases by 1.
- Command "DOWN": Move down from (0, 1) to (1, 1). The row index x increases by 1.
- Command "DOWN": Move further down to (2, 1). Again, x increases by 1.
- Command "LEFT": Move left to (2, 0). The column index y decreases by 1.
Final Calculation: The final position in 2D coordinates is (2, 0). Using the formula x * n + y, compute the 1D index: 2 * 3 + 0 = 6.
Return Result: The snake's final position is at index 6 in the grid.

So, after executing the given sequence of commands, the snake ends at the cell with a 1D index of 6.

Solution Implementation

1from typing import List
2
3class Solution:
4    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
5        # Initialize starting coordinates (x, y) as (0, 0)
6        x, y = 0, 0
7      
8        # Iterate through each command in the commands list
9        for command in commands:
10            # Check the first character of the command to determine direction
11            direction = command[0]
12          
13            # Update coordinates based on direction
14            if direction == "U":  # Move up
15                x -= 1  # Decrement x-coordinate
16            elif direction == "D":  # Move down
17                x += 1  # Increment x-coordinate
18            elif direction == "L":  # Move left
19                y -= 1  # Decrement y-coordinate
20            elif direction == "R":  # Move right
21                y += 1  # Increment y-coordinate
22      
23        # Return final position as single integer combining x and y
24        return x * n + y
25

1import java.util.List;
2
3class Solution {
4    public int finalPositionOfSnake(int n, List<String> commands) {
5        // Initialize starting coordinates
6        int x = 0, y = 0;
7      
8        // Iterate through each command in the list
9        for (String command : commands) {
10            // Determine direction and update position
11            switch (command.charAt(0)) {
12                case 'U': // Move up
13                    x--;
14                    break;
15                case 'D': // Move down
16                    x++;
17                    break;
18                case 'L': // Move left
19                    y--;
20                    break;
21                case 'R': // Move right
22                    y++;
23                    break;
24            }
25        }
26      
27        // Calculate and return the final linear position
28        return x * n + y;
29    }
30}
31

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to calculate the final position of the snake in a flattened grid
7    int finalPositionOfSnake(int n, std::vector<std::string>& commands) {
8        int x = 0, y = 0; // Initialize the starting position at (0, 0)
9      
10        // Iterate through the list of commands
11        for (const auto& command : commands) {
12            // Determine the direction based on the first character of the command
13            switch (command[0]) {
14            case 'U': 
15                x--; // Move up, decrement x
16                break;
17            case 'D': 
18                x++; // Move down, increment x
19                break;
20            case 'L': 
21                y--; // Move left, decrement y
22                break;
23            case 'R': 
24                y++; // Move right, increment y
25                break;
26            }
27        }
28      
29        // Calculate the final position in a linear array format
30        return x * n + y;
31    }
32};
33

1// This function calculates the final position of a snake on an n x n grid 
2// after executing a series of movement commands.
3function finalPositionOfSnake(n: number, commands: string[]): number {
4    // Initialize the starting position of the snake at the top-left corner (0, 0).
5    let [x, y] = [0, 0];
6  
7    // Iterate over each command in the commands array.
8    for (const command of commands) {
9        // Check the first character of each command to decide the movement direction.
10        if (command[0] === 'U') {
11            // Move up: decrease the x-coordinate.
12            x--;
13        } else if (command[0] === 'D') {
14            // Move down: increase the x-coordinate.
15            x++;
16        } else if (command[0] === 'L') {
17            // Move left: decrease the y-coordinate.
18            y--;
19        } else if (command[0] === 'R') {
20            // Move right: increase the y-coordinate.
21            y++;
22        }
23    }
24  
25    // Calculate the final position of the snake as a single index in the grid.
26    // Convert the 2D coordinates to a linear index.
27    return x * n + y;
28}
29

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the list commands. This is because each command in the list is processed once in a single iteration through the loop.

The space complexity of the code is O(1), as the code uses a constant amount of additional space regardless of the size of the input.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know