3661. Maximum Walls Destroyed by Robots

Description

There is an endless straight line populated with some robots and walls. You are given integer arrays robots, distance, and walls:

• 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:

• 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:

• 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:

• 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 <= 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

Solutions

Solution 1: Memoized Search

We first store each robot with its range in an array and sort them by robot position. We also sort the wall positions. Next, we use depth-first search (DFS) to calculate the number of walls each robot can destroy, and use memoized search to avoid redundant calculations.

We design a function \(\text{dfs}(i, j)\), where \(i\) represents the index of the current robot being considered, and \(j\) represents the firing direction of the next robot (0 for left, 1 for right), and returns the number of walls that can be destroyed. The answer is \(\text{dfs}(n - 1, 1)\), where \(j\) can be 0 or 1 in the boundary state.

The execution logic of function \(\text{dfs}(i, j)\) is as follows:

If \(i \lt 0\), it means all robots have been considered, return 0.

Otherwise, for the current robot, there are two firing directions to choose from.

If choosing to fire left, we need to calculate the left range \([\text{left}, \text{robot}[i][0]]\), and use binary search to calculate the number of walls that can be destroyed in this range. In this case, a total of \(\text{dfs}(i - 1, 0) + \text{count}\) walls can be destroyed, where \(\text{count}\) is the number of walls destroyed when the current robot fires left.

If choosing to fire right, we need to calculate the right range \([\text{robot}[i][0], \text{right}]\), and use binary search to calculate the number of walls that can be destroyed in this range. In this case, a total of \(\text{dfs}(i - 1, 1) + \text{count}\) walls can be destroyed, where \(\text{count}\) is the number of walls destroyed when the current robot fires right.

The return value of the function is the maximum number of walls that can be destroyed by the two firing directions.

Time complexity \(O(n \times \log n + m \times \log m)\), space complexity \(O(n)\). Where \(n\) and \(m\) are the numbers of robots and walls respectively.

Python3JavaC++GoTypeScript

class Solution:
    def maxWalls(self, robots: List[int], distance: List[int], walls: List[int]) -> int:
        n = len(robots)
        arr = sorted(zip(robots, distance), key=lambda x: x[0])
        walls.sort()

        @cache
        def dfs(i: int, j: int) -> int:
            if i < 0:
                return 0
            left = arr[i][0] - arr[i][1]
            if i > 0:
                left = max(left, arr[i - 1][0] + 1)
            l = bisect_left(walls, left)
            r = bisect_left(walls, arr[i][0] + 1)
            ans = dfs(i - 1, 0) + r - l
            right = arr[i][0] + arr[i][1]
            if i + 1 < n:
                if j == 0:
                    right = min(right, arr[i + 1][0] - arr[i + 1][1] - 1)
                else:
                    right = min(right, arr[i + 1][0] - 1)
            l = bisect_left(walls, arr[i][0])
            r = bisect_left(walls, right + 1)
            ans = max(ans, dfs(i - 1, 1) + r - l)
            return ans

        return dfs(n - 1, 1)

class Solution {
    private Integer[][] f;
    private int[][] arr;
    private int[] walls;
    private int n;

    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        n = robots.length;
        arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = robots[i];
            arr[i][1] = distance[i];
        }
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
        Arrays.sort(walls);
        this.walls = walls;
        f = new Integer[n][2];
        return dfs(n - 1, 1);
    }

    private int dfs(int i, int j) {
        if (i < 0) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }

        int left = arr[i][0] - arr[i][1];
        if (i > 0) {
            left = Math.max(left, arr[i - 1][0] + 1);
        }
        int l = lowerBound(walls, left);
        int r = lowerBound(walls, arr[i][0] + 1);
        int ans = dfs(i - 1, 0) + (r - l);

        int right = arr[i][0] + arr[i][1];
        if (i + 1 < n) {
            if (j == 0) {
                right = Math.min(right, arr[i + 1][0] - arr[i + 1][1] - 1);
            } else {
                right = Math.min(right, arr[i + 1][0] - 1);
            }
        }
        l = lowerBound(walls, arr[i][0]);
        r = lowerBound(walls, right + 1);
        ans = Math.max(ans, dfs(i - 1, 1) + (r - l));
        return f[i][j] = ans;
    }

    private int lowerBound(int[] arr, int target) {
        int idx = Arrays.binarySearch(arr, target);
        if (idx < 0) {
            return -idx - 1;
        }
        return idx;
    }
}

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        vector<pair<int, int>> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = {robots[i], distance[i]};
        }
        ranges::sort(arr, {}, &pair<int, int>::first);
        ranges::sort(walls);

        vector f(n, vector<int>(2, -1));

        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0) {
                return 0;
            }
            if (f[i][j] != -1) {
                return f[i][j];
            }

            int left = arr[i].first - arr[i].second;
            if (i > 0) {
                left = max(left, arr[i - 1].first + 1);
            }
            int l = ranges::lower_bound(walls, left) - walls.begin();
            int r = ranges::lower_bound(walls, arr[i].first + 1) - walls.begin();
            int ans = dfs(i - 1, 0) + (r - l);

            int right = arr[i].first + arr[i].second;
            if (i + 1 < n) {
                if (j == 0) {
                    right = min(right, arr[i + 1].first - arr[i + 1].second - 1);
                } else {
                    right = min(right, arr[i + 1].first - 1);
                }
            }
            l = ranges::lower_bound(walls, arr[i].first) - walls.begin();
            r = ranges::lower_bound(walls, right + 1) - walls.begin();
            ans = max(ans, dfs(i - 1, 1) + (r - l));

            return f[i][j] = ans;
        };

        return dfs(n - 1, 1);
    }
};

func maxWalls(robots []int, distance []int, walls []int) int {
    type pair struct {
        x, d int
    }
    n := len(robots)
    arr := make([]pair, n)
    for i := 0; i < n; i++ {
        arr[i] = pair{robots[i], distance[i]}
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i].x < arr[j].x
    })
    sort.Ints(walls)

    f := make(map[[2]int]int)

    var dfs func(int, int) int
    dfs = func(i, j int) int {
        if i < 0 {
            return 0
        }
        key := [2]int{i, j}
        if v, ok := f[key]; ok {
            return v
        }

        left := arr[i].x - arr[i].d
        if i > 0 {
            left = max(left, arr[i-1].x+1)
        }
        l := sort.SearchInts(walls, left)
        r := sort.SearchInts(walls, arr[i].x+1)
        ans := dfs(i-1, 0) + (r - l)

        right := arr[i].x + arr[i].d
        if i+1 < n {
            if j == 0 {
                right = min(right, arr[i+1].x-arr[i+1].d-1)
            } else {
                right = min(right, arr[i+1].x-1)
            }
        }
        l = sort.SearchInts(walls, arr[i].x)
        r = sort.SearchInts(walls, right+1)
        ans = max(ans, dfs(i-1, 1)+(r-l))

        f[key] = ans
        return ans
    }

    return dfs(n-1, 1)
}

function maxWalls(robots: number[], distance: number[], walls: number[]): number {
    type Pair = [number, number];
    const n = robots.length;
    const arr: Pair[] = robots.map((r, i) => [r, distance[i]]);

    _.sortBy(arr, p => p[0]).forEach((p, i) => (arr[i] = p));
    walls.sort((a, b) => a - b);
    const f: number[][] = Array.from({ length: n }, () => Array(2).fill(-1));

    function dfs(i: number, j: number): number {
        if (i < 0) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }

        let left = arr[i][0] - arr[i][1];
        if (i > 0) left = Math.max(left, arr[i - 1][0] + 1);
        let l = _.sortedIndex(walls, left);
        let r = _.sortedIndex(walls, arr[i][0] + 1);
        let ans = dfs(i - 1, 0) + (r - l);

        let right = arr[i][0] + arr[i][1];
        if (i + 1 < n) {
            if (j === 0) {
                right = Math.min(right, arr[i + 1][0] - arr[i + 1][1] - 1);
            } else {
                right = Math.min(right, arr[i + 1][0] - 1);
            }
        }
        l = _.sortedIndex(walls, arr[i][0]);
        r = _.sortedIndex(walls, right + 1);
        ans = Math.max(ans, dfs(i - 1, 1) + (r - l));

        f[i][j] = ans;
        return ans;
    }

    return dfs(n - 1, 1);
}

Comments