0923HardArrayBinary SearchDynamic ProgrammingSorting

Choosing Which Way Each Turret Fires

Tracked in this browser only

Trains the technique from

LeetCode 3661Maximum Walls Destroyed by Robots

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O((m + w) log w) for m turrets and w panels: one sort each and a constant number of searches per turret.Space O(m + w) for the sorted orders.

Sort the turrets by position, and sort the panels so that counting the panels in any stretch is a pair of binary searches. Because a shot is stopped by the neighbouring turret, one turret's sweep can only ever overlap the sweeps of the turrets directly beside it, and only in the gap between them. That locality is what makes a left-to-right pass work. Walk the turrets in order, holding two figures: the best total when this turret fired left, and the best total when it fired right. Firing right cannot overlap anything already settled, since everything to the left stops before this turret's position, so it simply adds its own sweep to the better of the previous two figures. Firing left may overlap the previous turret's rightward sweep, so that case adds its own sweep and then takes back the panels counted twice, which is the count over the intersection of the two stretches. Taking the better of the two figures at the end gives the answer.

Pythonentry point: max_walls

def max_walls(robots, distance, walls):
    import bisect
    order = sorted(range(len(robots)), key=lambda i: robots[i])
    spots = [robots[i] for i in order]
    reach = [distance[i] for i in order]
    panels = sorted(walls)
    m = len(spots)

    def count(lo, hi):
        if lo > hi:
            return 0
        return bisect.bisect_right(panels, hi) - bisect.bisect_left(panels, lo)

    def left_edge(i):
        edge = spots[i] - reach[i]
        if i > 0 and edge < spots[i - 1] + 1:
            edge = spots[i - 1] + 1
        return edge

    def right_edge(i):
        edge = spots[i] + reach[i]
        if i + 1 < m and edge > spots[i + 1] - 1:
            edge = spots[i + 1] - 1
        return edge

    went_left = count(left_edge(0), spots[0])
    went_right = count(spots[0], right_edge(0))
    for i in range(1, m):
        lo = left_edge(i)
        mine_left = count(lo, spots[i])
        mine_right = count(spots[i], right_edge(i))
        # firing left may cover panels the turret before already swept rightwards
        shared_lo = lo if lo > spots[i - 1] else spots[i - 1]
        shared_hi = right_edge(i - 1)
        if shared_hi > spots[i]:
            shared_hi = spots[i]
        shared = count(shared_lo, shared_hi)
        best_left = went_left + mine_left
        if went_right + mine_left - shared > best_left:
            best_left = went_right + mine_left - shared
        best_right = (went_left if went_left > went_right else went_right) + mine_right
        went_left = best_left
        went_right = best_right
    return went_left if went_left > went_right else went_right

The obvious version

Try every way of pointing the turrets, work out the set of positions swept, and count the panels inside it. Exponential in the turret count and it never reasons about which sweeps can overlap.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_walls(robots, distance, walls):
    order = sorted(range(len(robots)), key=lambda i: robots[i])
    spots = [robots[i] for i in order]
    reach = [distance[i] for i in order]
    m = len(spots)
    best = 0
    for mask in range(1 << m):
        covered = set()
        for i in range(m):
            if mask >> i & 1:
                lo = spots[i] - reach[i]
                if i > 0 and lo < spots[i - 1] + 1:
                    lo = spots[i - 1] + 1
                hi = spots[i]
            else:
                lo = spots[i]
                hi = spots[i] + reach[i]
                if i + 1 < m and hi > spots[i + 1] - 1:
                    hi = spots[i + 1] - 1
            for x in walls:
                if lo <= x <= hi:
                    covered.add(x)
        if len(covered) > best:
            best = len(covered)
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in