NeetCode #376LC-2751HardStack
← Back to All Problems#376 · #2751 · Robot Collisions(机器人碰撞)
📌 Problem Statement & Constraints
You are given arrays
positions, healths and directions describing robots. Robots move in their direction at the same speed; when two moving toward each other collide, the one with less health is destroyed and the other loses 1 health; equal health destroys both. Robots moving apart never collide. Return the healths of the surviving robots in the original input order. Constraints: 1 <= n <= 10^5; positions are distinct.💡 Core Algorithmic Approaches
- Sort the robots by position so collisions are processed left to right.
- A stack holds the indices of surviving right-movers. A left-mover can only collide with right-movers on the stack.
- Resolve collisions as in Asteroid Collision, but with health decrements rather than outright destruction.
- Collect the survivors' healths in the original index order.
💻 Benchmark Python3 Implementation
class Solution:
def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
n = len(positions)
order = sorted(range(n), key=lambda i: positions[i])
health = healths[:]
alive = [True] * n
st = [] # indices of surviving right-movers
for i in order:
if directions[i] == "R":
st.append(i)
continue
# a left-mover fights the right-movers on the stack
while st:
j = st[-1]
if health[j] < health[i]:
health[i] -= 1
alive[j] = False
st.pop()
elif health[j] > health[i]:
health[j] -= 1
alive[i] = False
break
else:
alive[j] = False
alive[i] = False
st.pop()
break
# if the stack emptied, the left-mover survives untouched
return [health[i] for i in range(n) if alive[i]]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the collision resolution is amortised O(n).
💾 Space Complexity
O(n) for the stack and the bookkeeping arrays.
⚠️ Interview Pitfalls & Follow-ups
- Not sorting by position: collisions would be resolved in the wrong order and the results would be wrong.
- Comparing the original
healthsafter modification: the mutablehealthcopy must be used throughout. - Returning the healths in sorted order: the answer must follow the original input order, hence the final loop over
range(n). - Forgetting that a left-mover surviving the whole stack keeps its full health: when the stack empties,
alive[i]is stillTrue, which is correct. - Treating robots moving apart as colliding: only opposing pairs on the stack interact, which the
R/Lhandling enforces.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.