Robot Collisions — LeetCode 2751 Python Solution
HardStackArraySortingSimulation
- Problem
- #2751
- Pattern
- Stack
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There are n 1-indexed robots, each having a position on a line, health, and movement direction. You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right).
Example
- Input
- positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
- Output
- [2,17,9,15,10]
- Explanation
- No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].
Python solution
Python
class Solution:
def survivedRobotsHealths(
self, positions: List[int], healths: List[int], directions: str
) -> List[int]:
n = len(positions)
indices = list(range(n))
stack = []
indices.sort(key=lambda i: positions[i])
for currentIndex in indices:
if directions[currentIndex] == "R":
stack.append(currentIndex)
else:
while stack and healths[currentIndex] > 0:
topIndex = stack.pop()
if healths[topIndex] > healths[currentIndex]:
healths[topIndex] -= 1
healths[currentIndex] = 0
stack.append(topIndex)
elif healths[topIndex] < healths[currentIndex]:
healths[currentIndex] -= 1
healths[topIndex] = 0
else:
healths[currentIndex] = 0
healths[topIndex] = 0
result = [health for health in healths if health > 0]
return resultComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2751. Robot Collisions is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2751. Robot Collisions?
- LeetCode 2751. Robot Collisions is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2751. Robot Collisions?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2751. Robot Collisions?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2751. Robot Collisions cover?
- LeetCode 2751. Robot Collisions is tagged Stack, Array, Sorting and Simulation on LeetCode.