Skip to content

3661. Maximum Walls Destroyed by Robots

SourceWeekly Contest 464 Q4DifficultyHardRating2525

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

Thinking

Each robot fires left or right, clipped by its \(\textit{distance}\) and by neighbors. \(2^n\) assignments are impossible.

After sorting by position, robot \(i\)'s choice depends only on robot \(i+1\)'s direction. \(\textit{dfs}(i,j)\) is the best destruction after deciding \(i\) with the next direction equal to \(j\).

A left shot is blocked by the previous robot; a right shot is blocked by the next robot and, if that one also fires left, by its range. Binary search counts walls in the surviving interval; memoization removes duplicate states.

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.

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

        ans = dfs(n - 1, 1)
        dfs.cache_clear()
        return ans

 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
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;
    }
}

 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
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);
    }
};

 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
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)
}

 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
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);
}

Solution 2: Dynamic Programming

Thinking

Each robot fires left or right, clipped by its \(\textit{distance}\) and by neighbors. Trying all \(2^n\) assignments does not fit \(n\le 10^5\).

After sorting by position, robot \(i\)'s reachable interval depends only on robot \(i+1\)'s direction. \(f[i][j]\) is the best total through robot \(i\) when that next direction is \(j\): the better of a left shot plus \(f[i-1][0]\) and a right shot plus \(f[i-1][1]\).

Searching that recurrence still chains \(n\) calls and overflows the stack. The two states are filled from \(i=0\) upward, and binary search counts the walls inside each clipped interval.

We first store each robot with its range in an array and sort them by robot position. We also sort the wall positions.

Define \(f[i][j]\) as the number of walls that can be destroyed after considering robot \(i\), when the next robot fires in direction \(j\) (0 for left, 1 for right). The answer is \(f[n - 1][1]\). There is no next robot when \(i = n - 1\), so either value of \(j\) gives the same result. When \(i = 0\) there is no earlier state, and that prefix is 0.

We fill \(f\) for \(i\) from \(0\) to \(n - 1\). For the current robot there are two firing directions.

If it fires left, the range is \([\text{left}, \text{robot}[i][0]]\). Binary search counts the walls in that range. The total is \(f[i - 1][0] + \text{count}\), where \(\text{count}\) is the number of walls this robot destroys by firing left.

If it fires right, the range is \([\text{robot}[i][0], \text{right}]\). Binary search counts the walls in that range. The total is \(f[i - 1][1] + \text{count}\), where \(\text{count}\) is the number of walls this robot destroys by firing right.

\(f[i][j]\) is the larger of those two totals.

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

 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
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()
        f = [[0, 0] for _ in range(n)]
        for i in range(n):
            for j in range(2):
                left = arr[i][0] - arr[i][1]
                if i:
                    left = max(left, arr[i - 1][0] + 1)
                l = bisect_left(walls, left)
                r = bisect_left(walls, arr[i][0] + 1)
                ans = (f[i - 1][0] if i else 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, (f[i - 1][1] if i else 0) + r - l)
                f[i][j] = ans
        return f[n - 1][1]

 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
class Solution {
    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        int n = robots.length;
        int[][] 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);
        int[][] f = new int[n][2];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 2; ++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 = (i > 0 ? f[i - 1][0] : 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, (i > 0 ? f[i - 1][1] : 0) + (r - l));
                f[i][j] = ans;
            }
        }
        return f[n - 1][1];
    }

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

 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
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<vector<int>> f(n, vector<int>(2));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 2; ++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 = (i ? f[i - 1][0] : 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, (i ? f[i - 1][1] : 0) + (r - l));
                f[i][j] = ans;
            }
        }
        return f[n - 1][1];
    }
};

 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
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([][2]int, n)
    for i := 0; i < n; i++ {
        for j := 0; j < 2; j++ {
            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 := 0
            if i > 0 {
                ans = f[i-1][0]
            }
            ans += 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)
            prev := 0
            if i > 0 {
                prev = f[i-1][1]
            }
            ans = max(ans, prev+(r-l))
            f[i][j] = ans
        }
    }
    return f[n-1][1]
}

 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
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(0));

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < 2; ++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 = (i > 0 ? f[i - 1][0] : 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, (i > 0 ? f[i - 1][1] : 0) + (r - l));
            f[i][j] = ans;
        }
    }
    return f[n - 1][1];
}

Comments