Robot Bounded In Circle: From intuitive to optimized-Top Tech Companies & Investment Bank Tech Assessment (Java, Med)

• LeetCode 1041: Robot Bounded In Circle
• Companies: Apple, Goldman Sachs, Amazon, LinkedIn, ZScaler, Bloomberg, Airbnb, Nvidia, Blue Origin
• Topics: Math, String, Simulation
• Level: Medium

Problem Overview

The "Robot Bounded In Circle" problem asks us to determine whether a robot executing a sequence of instructions will eventually return to its starting position and orientation, creating a bounded cycle.

Given: A string of instructions containing:

• 'G': Move straight one unit in the current direction
• 'L': Turn 90 degrees left
• 'R': Turn 90 degrees right

Goal: Return true if the robot stays within a bounded area, false otherwise.

Key Insight

The crucial mathematical insight is that a robot can only be bounded if one of these conditions is met:

1. After one instruction cycle(4 times), it returns to the origin (0,0)
2. After one instruction cycle, it's not facing north (meaning it will eventually return through rotational symmetry)

This is because if the robot ends up at a non-origin position while still facing north, it will keep moving in the same direction indefinitely, creating an unbounded path.

Solution 1: Brute Force Simulation (O(4n) Time)

class Solution {
    int[] direction = {0,1};
    int[] start = {0, 0};
    public boolean isRobotBounded(String instructions) {
        for (int i=0; i<4; i++){
            for (char x : instructions.toCharArray()) {
                if (x == 'G') {
                    start[0] += direction[0];
                    start[1] += direction[1];
                } else if (x == 'L') {
                    // Turn left: (dx, dy) -> (-dy, dx)
                    int temp = direction[0];
                    direction[0] = -direction[1];
                    direction[1] = temp;
                } else if (x == 'R') {
                    // Turn right: (dx, dy) -> (dy, -dx)
                    int temp = direction[0];
                    direction[0] = direction[1];
                    direction[1] = -temp;
                }
            }
        } 
        return start[0] == 0 && start[1] == 0;
    }
}

How It Works

This solution simulates the robot's movement for exactly 4 cycles of instructions. Since the robot can only face 4 different directions (north, east, south, west), after at most 4 cycles, it must return to its starting position if it's bounded.

Time Complexity: O(4n) = O(n) where n is the length of instructions
Space Complexity: O(1)

Direction Transformation Logic

• Left turn: (dx, dy) → (-dy, dx)
• Right turn: (dx, dy) → (dy, -dx)

These transformations represent 90-degree rotations in a 2D coordinate system.

Solution 2: One-Pass Optimization (O(n) Time)

class Solution {
    public boolean isRobotBounded(String instructions) {
        // north = 0, east = 1, south = 2, west = 3
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // Initial position is in the center
        int x = 0, y = 0;
        // facing north
        int idx = 0;

        for (char i : instructions.toCharArray()) {
            if (i == 'L')
                idx = (idx + 3) % 4;
            else if (i == 'R')
                idx = (idx + 1) % 4;
            else {
                x += directions[idx][0];
                y += directions[idx][1];   
            }    
        }

        // after one cycle:
        // robot returns into initial position
        // or robot doesn't face north
        return (x == 0 && y == 0) || (idx != 0);
    }
}

How It Works

This optimized solution executes the instructions only once and checks the mathematical condition for boundedness. It uses a directions array to represent the four cardinal directions and efficiently handles rotations using modular arithmetic.

Time Complexity: O(n) where n is the length of instructions
Space Complexity: O(1)

Direction Handling

• Directions array: {{0,1}, {1,0}, {0,-1}, {-1,0}} represents North, East, South, West
• Left turn: (idx + 3) % 4 (equivalent to subtracting 1 with wrap-around)
• Right turn: (idx + 1) % 4

Mathematical Proof

The key insight relies on group theory and rotational symmetry:

1. If robot returns to origin after one cycle: Obviously bounded
2. If robot doesn't face north after one cycle: The robot's final direction creates a rotational pattern that will eventually bring it back to the origin

If the robot ends at position (x, y) facing direction d ≠ north, then after k cycles where k×d ≡ 0 (mod 4), the robot will have completed a full rotation and returned to the origin.

Performance Comparison

When to Use Each Solution

Solution 1 (Brute Force):

• When code clarity and intuitive understanding are prioritized
• During interviews to demonstrate understanding of the problem mechanics
• When dealing with very short instruction sequences

Solution 2 (Optimized):

• When performance is critical
• In production code where efficiency matters
• When demonstrating mathematical insight and optimization skills

Both solutions are excellent examples of how mathematical insight can transform a seemingly complex simulation problem into an elegant algorithmic solution.