We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Snake in Matrix

Number: 3533

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

A snake starts at cell 0 (top-left corner) of an n x n grid and follows a sequence of commands ("UP", "RIGHT", "DOWN", "LEFT"). Each cell in the grid is numbered as grid[i][j] = (i * n) + j. The snake never leaves the grid. The task is to simulate the snake's movement and return the final cell index where it ends up.

Key Insights

  • The grid is represented in a 1D manner using the index formula (row * n + col).
  • The snake always starts at cell 0, which maps to position (0, 0) in row and column form.
  • Each command changes the snake’s current coordinate (row, col).
  • Since the snake never goes out of bounds, no boundary checks are necessary, simplifying the simulation.
  • The final answer is computed by converting the final (row, col) back to a linear index.

Space and Time Complexity

Time Complexity: O(m), where m is the number of commands. Space Complexity: O(1), since only constant space is used for the row and column variables.

Solution

We approach the problem by simulating the snake's movement step by step. We start at coordinate (0, 0) corresponding to cell 0. For each command in the list, we update the row or column accordingly:

  • "UP" decreases the row by 1.
  • "DOWN" increases the row by 1.
  • "LEFT" decreases the column by 1.
  • "RIGHT" increases the column by 1. After processing all commands, we convert the final (row, col) coordinate into the required 1D cell index using the formula: index = (row * n + col).

Code Solutions

def snake_in_matrix(n, commands):
    # Initialize starting position at (0, 0)
    row, col = 0, 0
    # Process each movement command
    for command in commands:
        if command == "UP":
            row -= 1  # Move up decreases the row index
        elif command == "DOWN":
            row += 1  # Move down increases the row index
        elif command == "LEFT":
            col -= 1  # Move left decreases the column index
        elif command == "RIGHT":
            col += 1  # Move right increases the column index
    # Convert 2D coordinates to 1D index
    return row * n + col

# Example usage:
# n = 2, commands = ["RIGHT", "DOWN"]
# Expected output: 3 because grid becomes [[0, 1], [2, 3]]
print(snake_in_matrix(2, ["RIGHT", "DOWN"]))
← Back to All Questions