Description
robots, distance, and walls:robots[i]is the position of theithrobot.distance[i]is the maximum distance theithrobot's bullet can travel.walls[j]is the position of thejthwall.
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] = 4fires left withdistance[0] = 3, covering[1, 4]and destroyswalls[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] = 10fires left withdistance[0] = 5, covering[5, 10]and destroyswalls[0] = 5andwalls[2] = 7.robots[1] = 2fires left withdistance[1] = 1, covering[1, 2]and destroyswalls[1] = 2.- Thus, the answer is 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 <= 1051 <= walls.length <= 1051 <= robots[i], walls[j] <= 1091 <= distance[i] <= 105- All values in
robotsare unique - All values in
wallsare unique
Solutions
This is an optimized dynamic programming solution that computes the maximum walls each robot can destroy in linear time by using multiple pointers to track wall positions. It sorts robots and walls, then iterates through each robot while maintaining pointers to key wall boundaries. For each robot, it calculates how many walls it can destroy on the left side (positioning left of the robot) and right side (positioning right), then uses DP states (subLeft and subRight) to track the best maximum walls achievable. The clever part is the transition: it combines the previous robot's left/right states with the current robot's options, considering overlapping regions between adjacent robots to avoid double-counting walls. This greedy-DP hybrid efficiently finds the optimal placement in O(n + m) time.
/**
* @param {number[]} robots
* @param {number[]} distance
* @param {number[]} walls
* @return {number}
*/
function maxWalls(robots, distance, walls) {
const n = robots.length;
const robotDist = robots.map((r, i) => [r, distance[i]]);
robotDist.sort((a, b) => a[0] - b[0]);
walls.sort((a, b) => a - b);
const m = walls.length;
let rightPtr = 0,
leftPtr = 0,
curPtr = 0,
robotPtr = 0;
let prevLeft = 0,
prevRight = 0,
prevNum = 0;
let subLeft = 0,
subRight = 0;
for (let i = 0; i < n; i++) {
const [robotPos, robotDistVal] = robotDist[i];
while (rightPtr < m && walls[rightPtr] <= robotPos) {
rightPtr++;
}
const pos1 = rightPtr;
while (curPtr < m && walls[curPtr] < robotPos) {
curPtr++;
}
const pos2 = curPtr;
let leftBound = robotPos - robotDistVal;
if (i >= 1) {
leftBound = Math.max(
robotPos - robotDistVal,
robotDist[i - 1][0] + 1,
);
}
while (leftPtr < m && walls[leftPtr] < leftBound) {
leftPtr++;
}
const leftPos = leftPtr;
const currentLeft = pos1 - leftPos;
let rightBound = robotPos + robotDistVal;
if (i < n - 1) {
rightBound = Math.min(
robotPos + robotDistVal,
robotDist[i + 1][0] - 1,
);
}
while (rightPtr < m && walls[rightPtr] <= rightBound) {
rightPtr++;
}
const rightPos = rightPtr;
const currentRight = rightPos - pos2;
let currentNum = 0;
if (i > 0) {
while (robotPtr < m && walls[robotPtr] < robotDist[i - 1][0]) {
robotPtr++;
}
const pos3 = robotPtr;
currentNum = pos1 - pos3;
}
if (i === 0) {
subLeft = currentLeft;
subRight = currentRight;
} else {
const newsubLeft = Math.max(
subLeft + currentLeft,
subRight -
prevRight +
Math.min(currentLeft + prevRight, currentNum),
);
const newsubRight = Math.max(
subLeft + currentRight,
subRight + currentRight,
);
subLeft = newsubLeft;
subRight = newsubRight;
}
prevLeft = currentLeft;
prevRight = currentRight;
prevNum = currentNum;
}
return Math.max(subLeft, subRight);
}