You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the ith city. Each power station can provide power to every city in a fixed range. In other words, if the range is denoted by

maxPower.js

/**
 * @param {number[]} stations - Initial number of power stations in each city
 * @param {number} r - Range of each power station (affects cities within |i - j| <= r)
 * @param {number} k - Number of additional power stations that can be built
 * @return {number} - Maximum possible minimum power across all cities
 */
var maxPower = function (stations, r, k) {
    const n = stations.length;

    // Step 1: Build prefix sum array to quickly compute power in a range
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + stations[i];
    }

    // Helper: Compute total power received by city i
    const getPower = (i) => {
        const left = Math.max(0, i - r);
        const right = Math.min(n - 1, i + r);
        return prefix[right + 1] - prefix[left];
    };

    // Step 2: Check if we can achieve at least `x` power in every city
    const canAchieve = (x) => {
        const added = new Array(n).fill(0); // Tracks added stations
        let used = 0; // Total stations used so far
        let extra = 0; // Sliding sum of added stations affecting current city

        for (let i = 0; i < n; i++) {
            // Remove influence of stations added too far left to affect city i
            if (i - r - 1 >= 0) {
                extra -= added[i - r - 1];
            }

            // Current power at city i (original + added within range)
            const curPower = getPower(i) + extra;

            // If power is below target, add stations at the farthest right position
            if (curPower < x) {
                const need = x - curPower;
                const pos = Math.min(n - 1, i + r); // Best place to add stations

                if (used + need > k) return false; // Not enough stations left

                used += need;
                added[pos] += need;
                extra += need;
            }
        }

        return true;
    };

    // Step 3: Binary search for the highest minimum power we can achieve
    let low = 0, high = 1e18, ans = 0;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (canAchieve(mid)) {
            ans = mid;       // Mid is achievable, try for higher
            low = mid + 1;
        } else {
            high = mid - 1;  // Mid is too high, try lower
        }
    }

    return ans;
};