Show problems as
Classic problem #3661HardArrayBinary SearchDynamic ProgrammingSorting

Maximum Walls Destroyed by Robots

Real-world version: Choosing Which Way Each Turret Fires
Tracked in this browser only
Read Maximum Walls Destroyed by Robots on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Turrets stand on a line at the distinct positions given by robots, and turret i has a reach of distance[i]. Panels stand at the distinct positions given by walls.

Each turret fires exactly one shot, and you choose whether that shot goes left or right. A shot from a turret at position p with reach d sweeps every position from p out to d away in the chosen direction, p itself included, except that it is stopped short by the next turret in that direction: it never reaches or passes that turret's position.

A panel is broken when at least one shot sweeps its position. Return the greatest number of panels that can be broken.

Examples

Example 1

Input
robots = [5, 9], distance = [10, 10], walls = [4, 5, 6, 7, 8, 9, 10, 11]
Output
7

Both turrets firing right is best. The turret at 5 is stopped just short of the one at 9, so it sweeps 5 to 8 and breaks the panels at 5, 6, 7 and 8; the turret at 9 sweeps 9 to 19 and breaks those at 9, 10 and 11. That is seven, and only the panel at 4 is left.

Example 2

Input
robots = [10], distance = [3], walls = [7]
Output
1

Nothing blocks the single turret, so firing left sweeps 7 to 10 and breaks the one panel.

Example 3

Input
robots = [7, 8, 9], distance = [5, 5, 5], walls = [7, 8, 9]
Output
3

The turrets sit right beside each other, so every shot is stopped at once and sweeps only the turret's own position. All three panels sit under turrets, so all three break.

Constraints

  • 1 <= robots.length <= 10^5
  • robots.length == distance.length
  • 1 <= walls.length <= 10^5
  • 1 <= robots[i] <= 10^9
  • 1 <= walls[j] <= 10^9
  • 1 <= distance[i] <= 10^5
  • The positions in robots are all different
  • The positions in walls are all different

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_walls(robots: list[int], distance: list[int], walls: list[int]) -> int:
Java
public int maxWalls(int[] robots, int[] distance, int[] walls)

More on the same topics