algoadvance

Leetcode 874. Walking Robot Simulation

Problem Statement

You are given an array of integers commands representing the commands to control a robot. The robot starts at the origin (0, 0) and faces the positive Y-axis. Each integer in the commands array has the following meanings:

Additionally, you are given an array obstacles where obstacles[i] = [x_i, y_i] represents a barrier at coordinates (x_i, y_i).

The robot should simulate the movement given the commands while avoiding obstacles. The goal is to determine the maximum Euclidean distance from the origin (0, 0) to any point the robot reaches.

Clarifying Questions

  1. Are the obstacles always within the range of possible movements given in the commands?
    • Obstacles may be anywhere within the potential range of movement. A proper check needs to be in place to avoid collisions.
  2. Is there a guaranteed maximum size for the commands and obstacles?
    • For this problem, we will assume practical limits within reasonable bounds as defined in typical competitive programming constraints.
  3. Should diagonal movements be considered?
    • No, only horizontal and vertical movements based on the current facing direction will be considered.

Strategy

  1. Initialize Start Point and Directions:
    • Start at the origin (0, 0).
    • Use directional vectors to handle movement:
      • North: (0, 1)
      • East: (1, 0)
      • South: (0, -1)
      • West: (-1, 0)
  2. Process Commands:
    • Use a variable to keep track of the current direction index.
    • For each command:
      • Update the direction index when turning (-2 and -1).
      • Move forward according to the current direction for movement commands (1 to 9).
  3. Handle Obstacle Checking:
    • Use a set to store obstacle positions for quick lookup.
    • During movement, check for each step if there is an obstacle ahead and stop if there is.
  4. Calculate Maximum Distance:
    • Track the maximum Euclidean distance squared from the origin throughout the movement.

Code

#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // Direction vectors for north, east, south, west
        vector<pair<int, int>> directions = \{\{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        // Use a set to store the obstacle positions
        unordered_set<string> obstacleSet;
        for (auto& obs : obstacles) {
            obstacleSet.insert(to_string(obs[0]) + "," + to_string(obs[1]));
        }
        
        // Start at origin, facing north
        int x = 0, y = 0, d = 0; // direction index (north)
        int maxDist = 0;
        
        for (int command : commands) {
            if (command == -2) {
                // Turn left
                d = (d + 3) % 4;
            } else if (command == -1) {
                // Turn right
                d = (d + 1) % 4;
            } else {
                // Move forward
                for (int i = 0; i < command; ++i) {
                    int nx = x + directions[d].first;
                    int ny = y + directions[d].second;
                    if (obstacleSet.find(to_string(nx) + "," + to_string(ny)) == obstacleSet.end()) {
                        x = nx;
                        y = ny;
                        maxDist = max(maxDist, x * x + y * y);
                    } else {
                        break; // obstacle found, stop moving in this direction
                    }
                }
            }
        }
        return maxDist;
    }
};

Time Complexity

This ensures that even for larger inputs, the solution remains efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI