3982 Maximum Walls Destroyed By Robots
Maximum Walls Destroyed by Robots 
There is an endless straight line populated with some robots and walls. You are given integer arrays robots, distance, and walls:
1
2
3
robots[i] is the position of the ith robot.
distance[i] is the **maximum** distance the ith robot's bullet can travel.
walls[j] is the position of the jth wall.
Every robot has one bullet that can either fire to the left or the right **at most **distance[i] meters.
A bullet destroys every wall in its path that lies within its range. Robots are fixed obstacles: if a bullet hits another robot before reaching a wall, it immediately stops at that robot and cannot continue.
Return the maximum number of unique walls that can be destroyed by the robots.
Notes:
1
2
A wall and a robot may share the same position; the wall can be destroyed by the robot at that position.
Robots are not destroyed by bullets.
Example 1:
Input: robots = [4], distance = [3], walls = [1,10]
Output: 1
Explanation:
1
2
robots[0] = 4 fires **left** with distance[0] = 3, covering [1, 4] and destroys walls[0] = 1.
Thus, the answer is 1.
Example 2:
Input: robots = [10,2], distance = [5,1], walls = [5,2,7]
Output: 3
Explanation:
1
2
3
robots[0] = 10 fires **left** with distance[0] = 5, covering [5, 10] and destroys walls[0] = 5 and walls[2] = 7.
robots[1] = 2 fires **left** with distance[1] = 1, covering [1, 2] and destroys walls[1] = 2.
Thus, the answer is 3.
Example 3:
Input: robots = [1,2], distance = [100,1], walls = [10]
Output: 0
Explanation:
In this example, only robots[0] can reach the wall, but its shot to the right is blocked by robots[1]; thus the answer is 0.
Constraints:
1
2
3
4
5
6
1 <= robots.length == distance.length <= 105
1 <= walls.length <= 105
1 <= robots[i], walls[j] <= 109
1 <= distance[i] <= 105
All values in robots are **unique**
All values in walls are **unique**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution:
def maxWalls(
self, robots: List[int], distance: List[int], walls: List[int]
) -> int:
n = len(robots)
left = [0] * n
right = [0] * n
num = [0] * n
robots_to_distance = {}
for i in range(n):
robots_to_distance[robots[i]] = distance[i]
robots.sort()
walls.sort()
for i in range(n):
pos1 = bisect.bisect_right(walls, robots[i])
if i >= 1:
left_bound = max(
robots[i] - robots_to_distance[robots[i]], robots[i - 1] + 1
)
left_pos = bisect.bisect_left(walls, left_bound)
else:
left_pos = bisect.bisect_left(
walls, robots[i] - robots_to_distance[robots[i]]
)
left[i] = pos1 - left_pos
if i < n - 1:
right_bound = min(
robots[i] + robots_to_distance[robots[i]], robots[i + 1] - 1
)
right_pos = bisect.bisect_right(walls, right_bound)
else:
right_pos = bisect.bisect_right(
walls, robots[i] + robots_to_distance[robots[i]]
)
pos2 = bisect.bisect_left(walls, robots[i])
right[i] = right_pos - pos2
if i == 0:
continue
pos3 = bisect.bisect_left(walls, robots[i - 1])
num[i] = pos1 - pos3
sub_left, sub_right = left[0], right[0]
for i in range(1, n):
current_left = max(
sub_left + left[i],
sub_right - right[i - 1] + min(left[i] + right[i - 1], num[i]),
)
current_right = max(sub_left + right[i], sub_right + right[i])
sub_left, sub_right = current_left, current_right
return max(sub_left, sub_right)