Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The first subarray always contributes nums[0]. The other k - 1 starting positions must have largest and smallest indices at most dist apart, so they fit inside a window of dist + 1 positions after index zero. For any such window, choosing its k - 1 smallest values minimizes the remaining cost.

Approach

Maintain two ordered multisets of (value, index) pairs. small contains the k - 1 smallest pairs in the current window, and large contains the rest. Keep the sum of the values in small. Indices distinguish equal values.

Initialize the first window and move its largest pairs out of small until the required size remains. To slide, remove the outgoing pair. If it came from small, promote the smallest pair from large when available. Insert the incoming pair into small, then move its largest pair to large if needed. These steps restore both size and ordering.

Record the smallest maintained sum across all windows and add nums[0]. Every feasible set of starting positions fits in an examined window, and every selected set within a window meets the distance constraint.

class Solution:
    def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
        n = len(nums)
        small, large = SortedList(), SortedList()

        # intial window
        for i in range(1, dist + 2):
            small.add((nums[i], i))

        # fill small
        while len(small) >= k:
            large.add(small.pop(-1))

        # redistribute to large
        curr = sum(v for v, _ in small)
        res = curr

        for i in range(dist + 2, n):
            pkey = (nums[i - dist - 1], i - dist - 1)
            nkey = (nums[i], i)
            # remove left
            if pkey in small:
                small.discard(pkey)
                curr -= nums[i - dist - 1]
                if large:
                    l = large.pop(0)
                    small.add(l)
                    curr += l[0]
            elif pkey in large:
                large.discard(pkey)
            # add right
            small.add(nkey)
            curr += nums[i]
            if len(small) >= k:
                s = small.pop(-1)
                large.add(s)
                curr -= s[0]
            res = min(res, curr)

        return res + nums[0]

Complexity analysis

Let n = nums.length and d = dist + 1. JavaScript's two AVL multisets give O(n log d) worst-case time, including initialization, with constant-size pair comparisons. Python uses block-based SortedList containers, not balanced trees: their updates are documented as approximately logarithmic, giving a practical O(n log d) estimate rather than a strict worst-case guarantee. Block shifts, splits and merges admit a conservative O(d) bound per update and O(n*d) total time. Both versions use O(d) auxiliary space; the JavaScript AVL recursion is only O(log d) deep.