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 i^th robot.
distance[i] is the maximum distance the i^th robot's bullet can travel.
walls[j] is the position of the j^th 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 <= 10⁵
1 <= walls.length <= 10⁵
1 <= robots[i], walls[j] <= 10⁹
1 <= distance[i] <= 10⁵
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.

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.

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



// Solution 2
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;
    }
}

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



// Solution 2
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];
    }
};

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)



# Solution 2
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]

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



// Solution 2
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]
}

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

3661 - Maximum Walls Destroyed by Robots

3661. Maximum Walls Destroyed by Robots

Description

Solutions

Solution 1: Memoized Search

Solution 2: Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

3661. Maximum Walls Destroyed by Robots

Description

Solutions

Solution 1: Memoized Search

Solution 2: Dynamic Programming

All Problems

All Solutions