⚡Flashcard Drill➔
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

  1. Sort the robots by position so collisions are processed left to right.
  2. A stack holds the indices of surviving right-movers. A left-mover can only collide with right-movers on the stack.
  3. Resolve collisions as in Asteroid Collision, but with health decrements rather than outright destruction.
  4. 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 healths after modification: the mutable health copy 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 still True, which is correct.
  • Treating robots moving apart as colliding: only opposing pairs on the stack interact, which the R/L handling enforces.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems