Walking Robot Simulation — LeetCode 874 Python Solution
MediumArrayHash TableSimulation
- Problem
- #874
- Pattern
- Hash Map
- Reading time
- 3 min
- Source
- leetcode.com
The problem
A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot receives an array of integers commands, which represents a sequence of moves that it needs to execute.
Python solution
Python
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
dirs = (0, 1, 0, -1, 0)
s = {(x, y) for x, y in obstacles}
ans = k = 0
x = y = 0
for c in commands:
if c == -2:
k = (k + 3) % 4
elif c == -1:
k = (k + 1) % 4
else:
for _ in range(c):
nx, ny = x + dirs[k], y + dirs[k + 1]
if (nx, ny) in s:
break
x, y = nx, ny
ans = max(ans, x * x + y * y)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 874. Walking Robot Simulation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 874. Walking Robot Simulation?
- LeetCode 874. Walking Robot Simulation is rated Medium on LeetCode.
- What is the time complexity of LeetCode 874. Walking Robot Simulation?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 874. Walking Robot Simulation?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 874. Walking Robot Simulation cover?
- LeetCode 874. Walking Robot Simulation is tagged Array, Hash Table and Simulation on LeetCode.