Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Robots block bullets, so walls strictly between two neighboring robots can be destroyed only by the left robot shooting right, the right robot shooting left, or both. This makes interactions local. A two-state dynamic program remembers the current robot's shooting direction while processing gaps.

Approach

Sort robots with their ranges and sort wall positions. Use binary searches to count walls in any inclusive interval. For each neighboring pair, clip both inward shooting ranges to the open gap between the robots. Count walls hit by either shot and subtract their intersection when both shoot.

Let state zero mean the current robot shoots right and state one mean it shoots left. Transition to each direction of the next robot, adding the appropriate gap count: left shot only, right shot only, both, or neither. Initialize a left-shooting first robot with walls reachable outside the left edge. A sentinel robot beyond all positions handles the last robot's rightward exterior range.

Finally add walls located exactly at robot positions separately; each can be destroyed by its colocated robot regardless of direction. Excluding robot positions from all gap counts prevents double counting.

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        walls.sort()

        def count(l, r):
            if l > r:
                return 0
            return bisect.bisect_right(walls, r) - bisect.bisect_left(walls, l)

        n = len(robots)
        arr = []
        for i in range(n):
            arr.append([robots[i], distance[i]])

        arr.sort()
        arr.append([inf, 0])  # sentinel
        dp = [[0] * 2 for _ in range(n + 1)]
        dp[0][1] = count(arr[0][0] - arr[0][1], arr[0][0] - 1)

        for i in range(n):
            l, ld = arr[i]
            r, rd = arr[i + 1]
            left1, right1 = l + 1, min(l + ld, r - 1)
            left2, right2 = max(r - rd, l + 1), r - 1
            left_count = count(left1, right1)
            right_count = count(left2, right2)
            both_count = left_count + right_count - count(max(left1, left2), min(right1, right2))
            dp[i + 1][0] = max(
                dp[i][0] + left_count,  # left shoots right
                dp[i][1]  # nothing
            )
            dp[i + 1][1] = max(
                dp[i][1] + right_count,  # right shoots left
                dp[i][0] + both_count  # both shoot
            )

        res = dp[-1][1]
        for pos, _ in arr:
            res += (count(pos, pos))

        return res

Complexity analysis

Let R = robots.length and W = walls.length. Time: O((R + W) log W + R log R). Auxiliary space: O(R + W) for sorted arrays and two-state DP.