There is an n x n grid, with the top-left cell at (0, 0) and the bottom-right cell at (n - 1, n - 1). You are given the integer n and an integer array startPos where startPos = [startrow, startcol] indicates that a robot is initially at cell (startrow, startcol).
You are also given a 0-indexed string s of length m where s[i] is the ith instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down).
The robot can begin executing from any ith instruction in s. It executes the instructions one by one towards the end of s but it stops if either of these conditions is met:
Return an array answer of length m where answer[i] is the number of instructions the robot can execute if the robot begins executing from the ith instruction in s.
Example 1:
Input: n = 3, startPos = [0,1], s = "RRDDLU" Output: [1,5,4,3,1,0] Explanation: Starting from startPos and beginning execution from the ith instruction: - 0th: "RRDDLU". Only one instruction "R" can be executed before it moves off the grid. - 1st: "RDDLU". All five instructions can be executed while it stays in the grid and ends at (1, 1). - 2nd: "DDLU". All four instructions can be executed while it stays in the grid and ends at (1, 0). - 3rd: "DLU". All three instructions can be executed while it stays in the grid and ends at (0, 0). - 4th: "LU". Only one instruction "L" can be executed before it moves off the grid. - 5th: "U". If moving up, it would move off the grid.
Example 2:
Input: n = 2, startPos = [1,1], s = "LURD" Output: [4,1,0,0] Explanation: - 0th: "LURD". - 1st: "URD". - 2nd: "RD". - 3rd: "D".
Example 3:
Input: n = 1, startPos = [0,0], s = "LRUD" Output: [0,0,0,0] Explanation: No matter which instruction the robot begins execution from, it would move off the grid.
Constraints:
m == s.length1 <= n, m <= 500startPos.length == 20 <= startrow, startcol < ns consists of 'L', 'R', 'U', and 'D'.This approach involves simulating the robot's moves starting from each instruction, checking if the robot stays within bounds of the grid. For each starting instruction, follow the operations one by one and update the robot's position accordingly, ensuring the position remains valid.
The solution iterates over each starting point in the instruction string. It simulates the movement of the robot using loops while checking the boundary conditions at each step. If at any point the robot moves outside the grid, the simulation for that start point stops and the count is stored in the result array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m^2), where m is the length of the instruction string, as each starting position requires checking over subsequent instructions.
Space Complexity: O(1) additional space besides the output.
Instead of simulating each path naively, another approach tackles the problem in reverse. By precomputing the effect of reversing each instruction and stopping at grid limits, we can gradually build up the result array.
The C program back-calculates from the end of the instruction string, storing lengths of valid paths in a backward manner to eventually obtain all initially possible move counts.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m^2), as each position from the end checks forward.
Space Complexity: O(1) besides output storage.
| Approach | Complexity |
|---|---|
| Simulation for Each Starting Instruction | Time Complexity: O(m^2), where m is the length of the instruction string, as each starting position requires checking over subsequent instructions. |
| Precomputing and Reverse Simulation | Time Complexity: O(m^2), as each position from the end checks forward. |
Product of Array Except Self - Leetcode 238 - Python • NeetCode • 747,485 views views
Watch 9 more video solutions →Practice Execution of All Suffix Instructions Staying in a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor