Minimum cost to clear a binary array with k-wide windows

Brute force. Treat the set of remaining 1s as a state and try every
removal: for each 1, its cheapest operation is the smallest window of length
k that contains it. Memoized over subsets this is O(2^m * m * k), which is
fine for checking answers but not for real input sizes. It is still worth
saying aloud, because running it on small cases shows the pattern.

Key observation: one number controls the answer. Let s be the smallest
number of 1s in any window of length k, and let m be the total number of 1s.

• Lower bound. Each operation pays the sum of some window, so it pays at
  least the current minimum window sum. One operation clears a single 1, so
  it lowers any window sum by at most 1, and the minimum drops by at most 1 per
  step. So step t (counting from 0) costs at least max(s - t, 1). The
  max(..., 1) is there because the chosen window always holds the 1 being
  cleared.
• Matching plan. Pick a window with exactly s ones and clear its 1s one by
  one, always paying for that same window: s + (s-1) + ... + 1. The window
  is now all zeros. Every 1 left in the array is now next to a run of at least
  k - 1 zeros. The window made of that run plus the 1 costs exactly 1, and
  clearing the 1 makes the zero run longer. So work outward from the window
  to the left and to the right, paying 1 for each remaining 1.

The bound and the plan agree, so

answer = s(s+1)/2 + (m - s)

s = 0 gives m, and k = n gives m(m+1)/2.
Computing s takes one sliding-window pass. The important point is that the
order of removal matters only until one window has been fully cleared. After
that, each remaining 1 costs exactly 1, which is also the lowest cost any
operation can have.

Invariant used by the plan. In phase 2, the zero block always contains
the cleared window, and it reaches up to the next 1 on each side. So a window
of length k that ends (or starts) at that 1 holds no other 1. The window
always fits inside the array: going left, i < l* <= n - k; going right,
i - k + 1 > l*.

from typing import List, Tuple


def min_conversion_cost(product: List[int], k: int) -> int:
    """Minimum total cost to turn every 1 into 0."""
    n = len(product)
    if not 1 <= k <= n:
        raise ValueError("k must satisfy 1 <= k <= len(product)")
    m = sum(product)
    if m == 0:
        return 0

    # s = smallest number of ones in any window of length k.
    window = sum(product[:k])
    s = window
    for r in range(k, n):
        window += product[r] - product[r - k]
        s = min(s, window)

    # Lower bound: step t costs at least max(s - t, 1); the plan below meets it.
    # Steps 0..s-1 cost s, s-1, ..., 1; the remaining m - s steps cost 1 each.
    return s * (s + 1) // 2 + (m - s)


def conversion_plan(product: List[int], k: int) -> List[Tuple[int, int, int]]:
    """One optimal sequence of operations as (l, index_cleared, cost)."""
    a = list(product)
    n = len(a)
    sums = [sum(a[l:l + k]) for l in range(n - k + 1)]
    best_l = min(range(n - k + 1), key=lambda l: sums[l])
    ops: List[Tuple[int, int, int]] = []

    # Phase 1: empty the sparsest window, always paying for that window.
    for i in range(best_l, best_l + k):
        if a[i]:
            ops.append((best_l, i, sum(a[best_l:best_l + k])))
            a[i] = 0

    # Phase 2: grow the zero block outward; each next 1 sits next to
    # k - 1 zeros, so a window holding only it costs 1.
    for i in range(best_l - 1, -1, -1):          # leftward
        if a[i]:
            ops.append((i, i, 1))
            a[i] = 0
    for i in range(best_l + k, n):               # rightward
        if a[i]:
            ops.append((i - k + 1, i, 1))
            a[i] = 0
    return ops


if __name__ == "__main__":
    assert min_conversion_cost([1, 1, 1], 2) == 4
    assert min_conversion_cost([0, 0, 0], 2) == 0
    assert min_conversion_cost([1, 1, 1, 1, 1, 1], 6) == 21
    assert min_conversion_cost([1, 1, 1, 1, 1, 1], 3) == 9
    assert min_conversion_cost([0, 1, 1, 1, 1, 0], 4) == 7
    assert min_conversion_cost([1, 0, 1, 1, 0, 1], 1) == 4
    assert min_conversion_cost([1], 1) == 1
    for p, k in [([1, 1, 1], 2), ([0, 1, 1, 1, 1, 0], 4), ([1, 1, 0, 1, 1, 1, 0, 1], 3)]:
        plan = conversion_plan(p, k)
        assert sum(c for _, _, c in plan) == min_conversion_cost(p, k)
    print("ok")

• min_conversion_cost: O(n) time for one sliding-window pass, O(1)
  extra space.
• conversion_plan: O(n * k) time as written, because it recomputes window
  sums for clarity. Keeping a running sum makes it O(n). O(n) space for
  the copy and the list of operations.
• Brute force (used only for checking): O(2^m * m * k).

• product = [1, 1, 1], k = 2 -> 4 (s = 2: pay 2 to clear index 1, then 1 + 1)
• product = [0, 0, 0], k = 2 -> 0 (nothing to do)
• product = [1], k = 1 -> 1
• product = [1, 0, 1, 1, 0, 1], k = 1 -> 4 (k = 1: every 1 costs 1)
• product = [1, 1, 1, 1, 1, 1], k = 6 -> 21 (one window covers everything: 6+5+...+1)
• product = [1, 1, 1, 1, 1, 1], k = 3 -> 9 (3+2+1 then three 1s at cost 1)
• product = [0, 1, 1, 1, 1, 0], k = 4 -> 7 (edge windows hold 3 ones; the middle window holds 4 but is never the cheapest)
• product = [1, 1, 0, 1, 1, 1, 0, 1], k = 3 -> s = 2, m = 6 -> 3 + 4 = 7
• A window with zero 1s already present -> answer is exactly m.
• Checked exhaustively against the subset brute force for every array with n <= 10 and every k. Each generated plan was replayed operation by operation as well.

1. Return the operations, not just the cost. Use conversion_plan. Clear
   the sparsest window while paying for it each time, then sweep outward
   paying 1 per remaining 1. Interviewers often ask for this to confirm the
   formula is achievable.
2. Point updates and queries. The array changes over time (a 0 becomes a
   1 or the reverse), and each query asks for the current answer. Keep the
   window sums W[l] in a segment tree that supports range add and range
   minimum. Flipping position i adds +/-1 to W[max(0, i-k+1) .. min(i, n-k)].
   Track m as a counter. Each update and query is O(log n).
3. Many values of k. For each k, s(k) is the minimum over windows
   of length k. With prefix sums each k costs O(n), so all k cost
   O(n^2). If the question only asks for the k that minimizes or reaches
   a budget, s(k) never decreases as k grows, so the answer is monotone
   in k and binary search works.
4. Weighted products / cost = sum of weights. If each position has a
   weight and an operation costs the current weight in the window, the
   one-step-at-a-time bound no longer has a simple closed form. Clearing the
   cheapest window is still a valid plan, but the order inside the window
   matters (clear the heaviest first). Talk through the exchange argument.
5. Circular conveyor. Windows wrap around. Compute s over the doubled
   array, limited to windows that start in [0, n). The rest of the argument
   does not change.

Mid-level (L4)

• Reads the operation correctly: the cost is the sum before the flip, and only one 1 is cleared per operation.
• Gets a correct brute force or simulation, and finds the [1, 1, 1], k = 2 -> 4 case by hand.
• With a hint ("what happens once a window is all zeros?"), reaches the formula and codes the sliding window.

Senior (L5)

• Finds on their own that, after one window is cleared, every remaining 1 costs exactly 1.
• Proves optimality with the "the minimum window sum drops by at most 1 per step" lower bound, not just by checking examples.
• Handles the edges (s = 0, k = 1, k = n, an all-zero array) and the boundary windows that cannot extend past the array.

Staff (L6+)

• Gives the argument and the code in a few minutes, then produces the explicit plan and explains why every phase-2 window fits inside the array.
• Extends cleanly to the dynamic version (segment tree with range add and range minimum) and the circular version, and explains where the closed form breaks under weights.
• Brings up testing: a small exhaustive brute-force oracle plus a replay checker that validates each emitted operation.