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

maxWalls.js

/**
 * @param {number[]} robots
 * @param {number[]} distance
 * @param {number[]} walls
 * @return {number}
 */
var maxWalls = function(robots, distance, walls) {
    // -----------------------------
    // 1. Sort robots and pair with distances
    // -----------------------------
    const n = robots.length;
    let arr = robots.map((pos, i) => [pos, distance[i]]);
    arr.sort((a, b) => a[0] - b[0]); // sort by robot position

    const R = arr.map(x => x[0]); // sorted robot positions
    const D = arr.map(x => x[1]); // sorted distances

    // -----------------------------
    // 2. Sort walls
    // -----------------------------
    walls.sort((a, b) => a - b);

    // Binary search helpers
    function lowerBound(arr, x) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            let mid = (lo + hi) >> 1;
            if (arr[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    function upperBound(arr, x) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            let mid = (lo + hi) >> 1;
            if (arr[mid] <= x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // -----------------------------
    // 3. Compute left/right intervals for each robot
    // -----------------------------
    const intervals = Array(n).fill(0).map(() => ({
        leftStart: 0, leftEnd: 0,
        rightStart: 0, rightEnd: 0
    }));

    for (let i = 0; i < n; i++) {
        const pos = R[i];
        const dist = D[i];

        // LEFT interval
        let L = pos - dist;
        if (i > 0) L = Math.max(L, R[i - 1]); // stops at previous robot
        intervals[i].leftStart = L;
        intervals[i].leftEnd = pos;

        // RIGHT interval
        let Rint = pos + dist;
        if (i < n - 1) Rint = Math.min(Rint, R[i + 1]); // stops at next robot
        intervals[i].rightStart = pos;
        intervals[i].rightEnd = Rint;
    }

    // -----------------------------
    // 4. Convert intervals → wall index ranges
    // -----------------------------
    const wallRanges = intervals.map(intv => {
        const lStartIdx = lowerBound(walls, intv.leftStart);
        const lEndIdx = upperBound(walls, intv.leftEnd) - 1;

        const rStartIdx = lowerBound(walls, intv.rightStart);
        const rEndIdx = upperBound(walls, intv.rightEnd) - 1;

        return { lStartIdx, lEndIdx, rStartIdx, rEndIdx };
    });

    // -----------------------------
    // 5. DP setup
    // dp[i][0] = max walls if robot i shoots LEFT
    // dp[i][1] = max walls if robot i shoots RIGHT
    //
    // last[i][*] = last wall index destroyed in that DP state
    // -----------------------------
    const dp = Array(n).fill(0).map(() => [0, 0]);
    const last = Array(n).fill(0).map(() => [-1, -1]);

    // Helper to count new walls without double-counting
    function countNewWalls(startIdx, endIdx, prevEnd) {
        if (endIdx < startIdx) return 0; // no walls in interval
        const effectiveStart = Math.max(startIdx, prevEnd + 1);
        if (effectiveStart > endIdx) return 0;
        return endIdx - effectiveStart + 1;
    }

    // -----------------------------
    // 6. Initialize robot 0
    // -----------------------------
    dp[0][0] = Math.max(0, wallRanges[0].lEndIdx - wallRanges[0].lStartIdx + 1);
    last[0][0] = wallRanges[0].lEndIdx;

    dp[0][1] = Math.max(0, wallRanges[0].rEndIdx - wallRanges[0].rStartIdx + 1);
    last[0][1] = wallRanges[0].rEndIdx;

    // -----------------------------
    // 7. Fill DP for robots 1..n-1
    // -----------------------------
    for (let i = 1; i < n; i++) {
        const { lStartIdx, lEndIdx, rStartIdx, rEndIdx } = wallRanges[i];

        // --- Robot i shoots LEFT ---
        let bestLeft = 0;
        let bestLeftLast = -1;

        for (let prev = 0; prev < 2; prev++) {
            const prevVal = dp[i - 1][prev];
            const prevEnd = last[i - 1][prev];

            const newWalls = countNewWalls(lStartIdx, lEndIdx, prevEnd);
            const total = prevVal + newWalls;

            if (total > bestLeft) {
                bestLeft = total;
                bestLeftLast = Math.max(prevEnd, lEndIdx);
            }
        }

        dp[i][0] = bestLeft;
        last[i][0] = bestLeftLast;

        // --- Robot i shoots RIGHT ---
        let bestRight = 0;
        let bestRightLast = -1;

        for (let prev = 0; prev < 2; prev++) {
            const prevVal = dp[i - 1][prev];
            const prevEnd = last[i - 1][prev];

            const newWalls = countNewWalls(rStartIdx, rEndIdx, prevEnd);
            const total = prevVal + newWalls;

            if (total > bestRight) {
                bestRight = total;
                bestRightLast = Math.max(prevEnd, rEndIdx);
            }
        }

        dp[i][1] = bestRight;
        last[i][1] = bestRightLast;
    }

    // -----------------------------
    // 8. Final answer
    // -----------------------------
    return Math.max(dp[n - 1][0], dp[n - 1][1]);
};