You are given a 0-indexed array of integers nums of length n, and two positive integers k and dist. The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3. You need to divide num

minimumCost.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} dist
 * @return {number}
 */
var minimumCost = function(nums, k, dist) {
    const n = nums.length;
    const INF = Number.MAX_SAFE_INTEGER;

    // If we only need 1 subarray, it's just the whole array starting at 0.
    if (k === 1) return nums[0];

    let sum = 0;          // sum of values currently chosen (size = used.size, up to k-1)
    let ans = INF;
    const used = new Set(); // indices currently chosen as starts (k-1 smallest in window)

    // max heap by value: stores [value, index] for chosen elements
    const heapUsed = new MaxPriorityQueue({
        compare: (a, b) => b[0] - a[0]   // larger value = higher priority
    });

    // min heap by value: stores [value, index] for non-chosen elements in window
    const heapUnused = new MinPriorityQueue({
        compare: (a, b) => a[0] - b[0]   // smaller value = higher priority
    });

    for (let right = 1; right < n; right++) {
        // Window is (left, right], with constraint right - left - 1 <= dist
        // So left = right - dist - 1
        const left = right - dist - 1;

        // 1) Move left border: remove index `left` from the window if it exists
        if (left >= 1 && used.has(left)) {
            // If `left` was one of the chosen indices, un-choose it
            used.delete(left);
            sum -= nums[left];

            // Clean out-of-window entries from heapUnused (indices <= left are out)
            while (!heapUnused.isEmpty() && heapUnused.front()[1] <= left) {
                heapUnused.dequeue();
            }

            // Try to promote the smallest unused element into used
            if (!heapUnused.isEmpty()) {
                const [val, idx] = heapUnused.dequeue();
                heapUsed.enqueue([val, idx]);
                used.add(idx);
                sum += val;
            }
        }

        // Even if `left` was not chosen, we still must clean heapUnused
        if (left >= 0) {
            while (!heapUnused.isEmpty() && heapUnused.front()[1] <= left) {
                heapUnused.dequeue();
            }
        }

        // 2) Move right border: add index `right` into the window
        if (used.size < k - 1) {
            // We still need more chosen indices; just add this one
            heapUsed.enqueue([nums[right], right]);
            used.add(right);
            sum += nums[right];
        } else {
            // We already have k-1 chosen indices; maybe we can improve them
            // First, clean stale entries from heapUsed (those whose index is no longer in `used`)
            while (!heapUsed.isEmpty() && !used.has(heapUsed.front()[1])) {
                heapUsed.dequeue();
            }

            // If current value is smaller than the largest chosen value, swap them
            if (!heapUsed.isEmpty() && nums[right] < heapUsed.front()[0]) {
                const [val, idx] = heapUsed.dequeue();

                used.delete(idx);
                heapUnused.enqueue([val, idx]);

                heapUsed.enqueue([nums[right], right]);
                used.add(right);

                sum += nums[right] - val;
            } else {
                // Otherwise, this index is just an unused candidate
                heapUnused.enqueue([nums[right], right]);
            }
        }

        // 3) Update answer:
        // We only have a valid selection when:
        // - the window is fully formed (left >= 0)
        // - we actually have k-1 chosen indices
        if (left >= 0 && used.size === k - 1) {
            ans = Math.min(ans, sum);
        }
    }

    return nums[0] + ans;
};