3661. Maximum Walls Destroyed by Robots

Array
Greedy
Sorting
Binary Search
Dynamic Programming

TIME

O(n log n + m log m)

SPACE

O(n)

Intuition

Each robot can fire left OR right. Bullets are blocked by adjacent robots. Use DP to track the best outcome when each robot fires left vs right, accounting for overlapping wall coverage between adjacent robots.

Solution

Step 1: Sort Robots by Position

Sort robots by position to determine blocking by adjacent robots.

Step 2: Compute Intervals for Each Robot

For each robot at position p with range d:

Left shot interval: [max(p - d, prev_robot + 1), p] Right shot interval: [p, min(p + d, next_robot - 1)]

Use binary search to find wall indices within each interval.

Step 3: Count Walls and Overlaps

left[i] = walls destroyed if robot i fires left
right[i] = walls destroyed if robot i fires right
overlap[i] = walls in intersection of right[i-1] and left[i] intervals

Overlap matters because if robot i-1 fires right and robot i fires left, they may both cover the same walls (counted twice).

Step 4: DP Transition

Track two states:

sub_left = max walls if current robot fires left
sub_right = max walls if current robot fires right

For each robot i:

current_left = max(sub_left + left[i], sub_right + left[i] - overlap[i])
current_right = max(sub_left + right[i], sub_right + right[i])

The overlap subtraction handles double-counting when adjacent robots' ranges intersect.

Complexity

Time: O(n log n + m log m), sorting and binary search
Space: O(n), interval arrays and DP states

Edge Cases

Single robot → max of left or right shot
No walls in range → return 0
All robots blocking each other → minimal coverage
Walls at robot positions → included in both left and right

Code

from bisect import bisect_left, bisect_right
from typing import List


class Solution:
    def maxWallsDestroyed(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        """
        3661. Maximum Walls Destroyed by Robots
        Time: O(n log n + m log m)
        Space: O(n)
        """
        n = len(robots)
        robots_with_d = sorted(zip(robots, distance))
        robots = [r for r, _ in robots_with_d]
        dist = {r: d for r, d in robots_with_d}
        walls.sort()

        left_l = [0] * n
        left_r = [0] * n
        right_l = [0] * n
        right_r = [0] * n

        for i in range(n):
            p = robots[i]
            d = dist[p]

            L = p - d
            if i > 0:
                L = max(L, robots[i - 1] + 1)

            left_l[i] = bisect_left(walls, L)
            left_r[i] = bisect_right(walls, p) - 1

            R = p + d
            if i < n - 1:
                R = min(R, robots[i + 1] - 1)

            right_l[i] = bisect_left(walls, p)
            right_r[i] = bisect_right(walls, R) - 1

        def count(l, r):
            return max(0, r - l + 1)

        left = [count(left_l[i], left_r[i]) for i in range(n)]
        right = [count(right_l[i], right_r[i]) for i in range(n)]

        overlap = [0] * n
        for i in range(1, n):
            l = max(right_l[i - 1], left_l[i])
            r = min(right_r[i - 1], left_r[i])
            overlap[i] = max(0, r - l + 1)

        sub_left = left[0]
        sub_right = right[0]

        for i in range(1, n):
            current_left = max(
                sub_left + left[i],
                sub_right + left[i] - overlap[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)

import java.util.*;

/**
 * 3661. Maximum Walls Destroyed by Robots
 * Time: O(n log n + m log m)
 * Space: O(n)
 */
class Solution {
    public int maxWallsDestroyed(int[] robots, int[] distance, int[] walls) {
        int n = robots.length;

        int[][] robotsWithD = new int[n][2];
        for (int i = 0; i < n; i++) {
            robotsWithD[i][0] = robots[i];
            robotsWithD[i][1] = distance[i];
        }
        Arrays.sort(robotsWithD, (a, b) -> a[0] - b[0]);

        int[] pos = new int[n];
        Map<Integer, Integer> dist = new HashMap<>();
        for (int i = 0; i < n; i++) {
            pos[i] = robotsWithD[i][0];
            dist.put(robotsWithD[i][0], robotsWithD[i][1]);
        }

        Arrays.sort(walls);

        int[] leftL = new int[n];
        int[] leftR = new int[n];
        int[] rightL = new int[n];
        int[] rightR = new int[n];

        for (int i = 0; i < n; i++) {
            int p = pos[i];
            int d = dist.get(p);

            long L = p - d;
            if (i > 0) {
                L = Math.max(L, pos[i - 1] + 1);
            }

            leftL[i] = lowerBound(walls, L);
            leftR[i] = upperBound(walls, p) - 1;

            long R = p + d;
            if (i < n - 1) {
                R = Math.min(R, pos[i + 1] - 1);
            }

            rightL[i] = lowerBound(walls, p);
            rightR[i] = upperBound(walls, R) - 1;
        }

        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            left[i] = Math.max(0, leftR[i] - leftL[i] + 1);
            right[i] = Math.max(0, rightR[i] - rightL[i] + 1);
        }

        int[] overlap = new int[n];
        for (int i = 1; i < n; i++) {
            int l = Math.max(rightL[i - 1], leftL[i]);
            int r = Math.min(rightR[i - 1], leftR[i]);
            overlap[i] = Math.max(0, r - l + 1);
        }

        int subLeft = left[0];
        int subRight = right[0];

        for (int i = 1; i < n; i++) {
            int currentLeft = Math.max(
                subLeft + left[i],
                subRight + left[i] - overlap[i]
            );

            int currentRight = Math.max(
                subLeft + right[i],
                subRight + right[i]
            );

            subLeft = currentLeft;
            subRight = currentRight;
        }

        return Math.max(subLeft, subRight);
    }

    private int lowerBound(int[] arr, long target) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) / 2;
            if (arr[mid] < target) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    private int upperBound(int[] arr, long target) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) / 2;
            if (arr[mid] <= target) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}