Fewest decrements to make an array a 1-to-k-to-1 pyramid

Every operation lowers one element by 1 and nothing can be raised. So the
final array is a target t with t[j] <= arr[j] everywhere, and the cost
is sum(arr) - sum(t). Minimizing operations is the same as maximizing
the sum of a valid target.

A valid target is fully described by two numbers: the peak index p and
the peak height h. It looks like

0 ... 0, 1, 2, ..., h-1, h, h-1, ..., 2, 1, 0 ... 0
                          ^ p

so t[j] = max(0, h - |j - p|) and its sum is 1 + 2 + ... + h + ... + 1 = h².
The whole answer is sum(arr) - max over p of h(p)², where h(p) is the
tallest pyramid that can stand at p.

Brute force. For each peak p, try heights from large to small and check
every position of the pyramid against arr. That is O(n²) or worse and is a
fine thing to say first, but n can be large.

What limits the height at p. Position j inside the pyramid needs
arr[j] >= h - |j - p|, i.e. h <= arr[j] + |j - p|. The pyramid also has to
fit in the array: its left foot (value 1) sits at p - h + 1 >= 0 and its
right foot at p + h - 1 <= n - 1. Position j outside the pyramid gives a
bound that is never tighter (for those j, arr[j] + |j-p| >= |j-p| >= h).
So

h(p) = min( min_j (arr[j] + |j - p|),  p + 1,  n - p )

Optimal: two linear passes. Split the min into a left part and a right
part, each computable incrementally:

• left[i] = min(arr[i], left[i-1] + 1), with left[0] = min(arr[0], 1).
  The 1 at index 0 is the "fits in the array" bound i + 1, carried along
  by the same +1 recurrence.
• right[i] = min(arr[i], right[i+1] + 1), with right[n-1] = min(arr[n-1], 1).

Then h(p) = min(left[p], right[p]). Invariant: left[i] is the tallest
strictly-increasing-by-one ramp ..., h-1, h that ends at i, fits under
arr, and starts from a 1 inside the array (or from zeros before it).
Symmetrically for right. A peak of height h needs both ramps.

If every element is 0, the best height is 0 and the answer is 0: an
all-zero array has an empty non-zero part, which we accept as bitonic.

from typing import List, Tuple


def min_ops_to_bitonic(arr: List[int]) -> int:
    """Minimum number of single decrements that turn arr into
    0..0, 1, 2, ..., k, ..., 2, 1, 0..0 (zeros optional)."""
    best_height, _ = best_pyramid(arr)
    return sum(arr) - best_height * best_height


def best_pyramid(arr: List[int]) -> Tuple[int, int]:
    """Return (height, peak_index) of the largest pyramid that fits under arr."""
    n = len(arr)
    if n == 0:
        return 0, -1

    left = [0] * n
    prev = 0  # ramp height just before index 0 (outside the array)
    for i in range(n):
        prev = min(arr[i], prev + 1)
        left[i] = prev

    best_height, best_peak = 0, -1
    prev = 0
    for i in range(n - 1, -1, -1):
        prev = min(arr[i], prev + 1)  # right[i]
        h = min(left[i], prev)
        if h > best_height:
            best_height, best_peak = h, i
    return best_height, best_peak


def target_array(arr: List[int]) -> List[int]:
    """The bitonic array the minimum-cost answer produces (for follow-ups)."""
    h, p = best_pyramid(arr)
    return [max(0, h - abs(j - p)) if h else 0 for j in range(len(arr))]


def brute_force(arr: List[int]) -> int:
    n, total, best = len(arr), sum(arr), 0
    for p in range(n):
        for h in range(1, n + 1):
            if all(arr[j] >= h - abs(j - p) for j in range(n)) and \
               p - h + 1 >= 0 and p + h - 1 < n:
                best = max(best, h * h)
    return total - best


if __name__ == "__main__":
    import random

    assert min_ops_to_bitonic([1, 2, 3, 2, 1]) == 0
    assert min_ops_to_bitonic([2, 5, 4, 6, 2]) == 10   # -> 1, 2, 3, 2, 1 (sum 9), total 19
    assert min_ops_to_bitonic([4, 4, 4, 4]) == 12      # -> 1,2,1,0 or 0,1,2,1
    assert min_ops_to_bitonic([0, 0, 0]) == 0
    assert min_ops_to_bitonic([7]) == 6
    assert min_ops_to_bitonic([]) == 0
    assert min_ops_to_bitonic([3, 1, 9, 9, 9, 1]) == 23
    assert target_array([5, 9, 9, 9, 5]) == [1, 2, 3, 2, 1]
    for _ in range(2000):
        a = [random.randint(0, 6) for _ in range(random.randint(1, 8))]
        assert min_ops_to_bitonic(a) == brute_force(a), a
    print("ok")

• Time: O(n), two passes over the array plus one sum.
• Space: O(n) for the left array. It can be O(1) extra if you store
  left in place or recompute; the right pass already uses a single
  running value.
• target_array is O(n) more to build the output.

• [1, 2, 3, 2, 1] → 0 (already bitonic).
• [2, 5, 4, 6, 2] → 10: best pyramid is 1, 2, 3, 2, 1 (sum 9), total 19.
• [4, 4, 4, 4] → 12: even length, best is height 2, e.g. 1, 2, 1, 0 (sum 4) out of 16.
• [3, 1, 9, 9, 9, 1] → 23: best is 0, 1, 2, 3, 2, 1 (peak at index 3, sum 9), total 32. A peak at index 2 is capped at 2 by the 1 at index 1.
• [0, 0, 0] → 0 (no non-zero part).
• [7] → 6 (single element becomes 1).
• [] → 0.
• [0, 5, 5, 5, 0] → 11: pyramid 0, 1, 2, 1, 0 (sum 4) out of 15.
• A huge spike: [1, 100, 1] → 98: target 1, 2, 1.

1. Return the resulting array, not just the count. Keep the argmax peak
   and height from the pass and emit max(0, h - |j - p|) (target_array).
   Ties: pick the leftmost peak, or ask the interviewer.
2. Operations can also increase elements by 1 (each costs 1). Now the
   cost of a fixed pyramid is sum |arr[j] - t[j]|, so the h² shortcut is
   gone and short peaks no longer win for free. A direct answer tries every
   (p, h) with prefix sums for the zero regions: O(n²). For a fixed peak the
   cost is convex in h, so ternary search on h per peak brings it to
   about O(n² log n) naive or O(n log² n) with sorted offsets
   arr[j] + |j - p| and prefix sums.
3. Peak height is fixed to k, or the pyramid must use the whole array
   (no zero prefix/suffix). For the whole-array case only odd n works, the
   peak is the middle, and h = (n+1)/2; check feasibility against arr in
   O(n). For a fixed k, slide a window of length 2k-1 and test the bound
   arr[j] + |j - p| >= k with the left/right arrays.
4. Online / streaming input. Elements arrive one by one and you must
   report the best answer so far. left is incremental, but every new
   element can lower right for earlier peaks. Since
   h(p) = min(p + 1, n - p, min_j(arr[j] + |j - p|)), keep segment trees
   over arr[j] - j and arr[j] + j and binary-search the best height per
   candidate peak, or recompute lazily only when a query arrives.
5. Non-strict slopes (plateaus allowed) or a step size other than 1.
   Generalize the recurrence to left[i] = min(arr[i], left[i-1] + step);
   the target sum is no longer h², so track the sum explicitly.

Mid-level (L4)

• Restates the problem as "maximize the kept sum" since decrements only.
• Gets an O(n²) solution working, then reaches the left/right pass with
  some hints.
• Handles the all-zero and single-element cases.

Senior (L5)

• Derives h(p) = min(arr[j] + |j - p|, p + 1, n - p) and the h² sum
  without hints, explains why positions outside the pyramid never bind.
• Writes the two-pass O(n) code cleanly and tests it against a brute force.
• Handles follow-up 1 and 3 quickly.

Staff (L6+)

• Proves the invariants of the ramp recurrences and the boundary trick
  (seeding with 0 outside the array encodes "the pyramid must fit").
• Reasons about the two-sided cost variant (follow-up 2) and the streaming
  variant with appropriate data structures.
• Discusses overflow (sums of large values), input validation (negative
  numbers), and how they would test it in production.