Implement two array-cost minimization algorithms

Implement two array-cost minimization algorithms that appeared back-to-back in an AWS SDE online assessment. Each can be solved independently.

Part 1 — Minimize total merge cost

You are given a list of positive integers workloads, where each value represents a task size. You may repeatedly pick any two items a and b, merge them into a single item of size a + b, and pay a cost of a + b for that merge. Repeat until a single item remains.

Implement:

minimizeSystemCost(workloads: int[]) -> long

returning the minimum possible total cost to reduce the list to one item. State the algorithm you use and its time/space complexity.

Hint: Reframe the cost

The final cost is the sum, over every merge, of the size of the item produced. Equivalently, each original item contributes its value once for every merge it participates in — i.e., its value times its depth in the merge tree. To minimize, large values should be merged last (shallow), small values merged first (deep).

Hint: Greedy structure

Always merging the two smallest current items is optimal — this is the optimal-merge / Huffman pattern. What data structure repeatedly hands you the two smallest elements and lets you insert the new sum back efficiently?

Hint: Watch the accumulation

A merged item's size is paid again every time it is merged further, so accumulate a + b into the running total at each pop-pop-push step, not just once. Also handle $n \le 1$ (cost is $0$).

Part 2 — Remove a contiguous block to minimize adjacent differences

You are given an integer array machines representing machine strengths and an integer k with $1 \le k < \text{machines.length}$. Remove exactly k consecutive elements. For the remaining sequence (kept in original order), define its cost as the sum over all adjacent pairs of $|\text{strength}[i] - \text{strength}[i+1]|$.

Implement:

minimizeRemainingAdjDiff(machines: int[], k: int) -> (long minCost, int startIndex)

returning the minimal achievable cost and a valid starting index of the removed block (the index of the first removed element). Target $O(n)$ or $O(n \log n)$.

Hint: Decompose the remaining cost

For a removed block at start s (covering indices s..s+k-1), the remaining sequence is a[0..s-1] followed by a[s+k..n-1]. Its adjacency cost splits into three independent pieces: adjacencies entirely inside the prefix, adjacencies entirely inside the suffix, and at most one new join between a[s-1] and a[s+k].

Hint: Prefix sums of differences

Let diff[i] = |a[i+1] - a[i]| and let P be its prefix sum. Any contiguous run of adjacencies is then a constant-time range query on P. With that, evaluating each candidate s is $O(1)$, so a single sweep over all valid s is $O(n)$.

Hint: Boundary cases

The join term exists only when both sides are non-empty — i.e. s >= 1 and s + k <= n - 1. When the removed block touches the start or the end, there is no join to add. Empty/one-element remainders have cost $0$.

Constraints & Assumptions

• Part 1: workloads values are positive integers; the result can exceed 32-bit range, so accumulate in a 64-bit integer (long). The list may be empty or a single element.
• Part 2: machines values are arbitrary integers (possibly negative); $1 \le k < n$ where $n =$ machines.length. Differences and their sums can exceed 32-bit range — use long. There are $n - k + 1$ valid start positions; ties may return any valid start.

Clarifying Questions to Ask

• Part 1: Can workloads be empty or have a single element? (Both should return cost $0$.)
• Part 1: Are values guaranteed positive, and how large can the total get (does it overflow 32-bit)?
• Part 2: Is k strictly less than n, guaranteeing at least one element survives?
• Part 2: If multiple start indices achieve the minimum cost, is any valid one acceptable, or is a specific tie-break (e.g. smallest index) required?
• Part 2: Can strengths be negative or zero? (Affects whether you can assume sorted/positive structure — you cannot.)

What a Strong Answer Covers

A strong submission treats these as two distinct problems and nails the optimal complexity for each:

• Part 1: identifies the optimal-merge / Huffman greedy, justifies why always merging the two smallest is optimal (depth argument), implements it with a min-heap in $O(n \log n)$ time / $O(n)$ space, accumulates each intermediate sum into the total, and handles the $n \le 1$ base case plus 64-bit overflow.
• Part 2: derives the prefix/suffix/join decomposition, uses prefix sums over the absolute-difference array for $O(1)$ candidate evaluation, achieves an $O(n)$ single sweep, correctly handles the no-join boundary cases (block at either end), and returns a valid start index along with the cost.
• Both: correct integer types to avoid overflow, clean handling of degenerate inputs, and clearly stated time/space complexity.

Follow-up Questions

• Part 1: If two specific items were forbidden from ever being merged directly, or merges were constrained to adjacent items only, how would the optimal strategy and complexity change?
• Part 1: How would you reconstruct and report the actual sequence of merges that achieves the minimum cost?
• Part 2: Suppose you must instead remove k consecutive elements to maximize the remaining adjacency cost — does the same decomposition still work? What changes?
• Part 2: If k were not fixed but bounded by a budget (remove up to k consecutive), how would you adapt the sweep?

Minimize Total Merge Cost (Optimal Merge / Huffman)

You are given a list of positive integers workloads, where each value is a task size. You may repeatedly pick any two items a and b, merge them into a single item of size a + b, and pay a cost of a + b for that merge. Repeat until a single item remains.

Implement minimizeSystemCost(workloads) -> long returning the minimum possible total cost to reduce the list to one item.

The final cost equals the sum over every merge of the produced item's size — equivalently, each original value times its depth in the merge tree. To minimize, always merge the two smallest current items (the optimal-merge / Huffman pattern), accumulating a + b into the running total at every pop-pop-push step. A list of length 0 or 1 needs no merges and costs 0. The total can exceed 32-bit range, so accumulate in a 64-bit integer.

Constraints

• workloads values are positive integers
• 0 <= len(workloads); the list may be empty or a single element (cost 0)
• The result can exceed 32-bit range; accumulate in a 64-bit integer (long)

Examples

Example 1

Input: ([4, 6, 8],)
Output: 28

Explanation: Merge 4+6=10 (cost 10), then 10+8=18 (cost 18). Total 28. Merging the two smallest first is optimal.

Example 2

Input: ([1, 2, 3, 4, 5],)
Output: 33

Explanation: 1+2=3 (3), 3+3=6 (6), 4+5=9 (9), 6+9=15 (15) -> 3+6+9+15 = 33.

Hints

1. Reframe: the total cost is the sum over every merge of the produced item's size, i.e. each original value times its depth in the merge tree. Large values should be merged last (shallow), small values first (deep).
2. Always merging the two smallest current items is optimal (optimal-merge / Huffman). Use a min-heap that hands you the two smallest and lets you push the sum back.
3. A merged item's size is paid again on every later merge, so add a + b to the running total at each pop-pop-push step, not just once. Handle n <= 1 (cost 0).

Remove a Contiguous Block to Minimize Adjacent Differences

You are given an integer array machines (machine strengths, possibly negative) and an integer k with 1 <= k < machines.length. Remove exactly k consecutive elements. For the remaining sequence (kept in original order), its cost is the sum over all adjacent pairs of |strength[i] - strength[i+1]|.

Implement minimizeRemainingAdjDiff(machines, k) -> (long minCost, int startIndex) returning the minimal achievable cost and a valid starting index of the removed block (the index of the first removed element). If several starts tie, the smallest valid start index is returned.

For a removed block at start s (indices s..s+k-1), the remaining cost splits into three independent pieces: prefix-internal adjacencies P[s-1] (when s >= 1), suffix-internal adjacencies P[n-1] - P[s+k] (when s+k <= n-1), and at most one join |a[s+k] - a[s-1]| that exists only when both sides are non-empty. Here P is the prefix sum of the absolute adjacent-difference array, making each candidate O(1) and the whole sweep O(n). Use 64-bit accumulation.

Constraints

• machines values are arbitrary integers (possibly negative or zero)
• 1 <= k < n where n = len(machines)
• There are n - k + 1 valid start positions; on ties the smallest valid start index is returned
• Differences and their sums can exceed 32-bit range; use 64-bit accumulation

Examples

Example 1

Input: ([1, 100, 2, 3, 4], 1)
Output: (3, 1)

Explanation: Removing the spike 100 (start 1) leaves [1,2,3,4] with cost 1+1+1=3, the minimum.

Example 2

Input: ([10, 1, 10, 1, 10], 2)
Output: (18, 0)

Explanation: Every removal of a length-2 block leaves an oscillating remainder; start 0 gives [10,1,10] -> 9+9=18, which is minimal (smallest index on tie).

Hints

1. For a block removed at start s, the remaining sequence is a[0..s-1] then a[s+k..n-1]. Its cost splits into prefix-internal adjacencies, suffix-internal adjacencies, and at most one new join between a[s-1] and a[s+k].
2. Let diff[i] = |a[i+1]-a[i]| and P its prefix sum. Any contiguous run of adjacencies is then a constant-time range query, so each candidate s is O(1) and the full sweep is O(n).
3. The join term exists only when both sides are non-empty: s >= 1 and s+k <= n-1. When the block touches the start or end there is no join. Empty/one-element remainders cost 0.

Solution

Two independent problems. Part 1 is the classic optimal-merge (Huffman) greedy; Part 2 is a prefix-sum sweep over candidate removal blocks.

Part 1 — Minimize total merge cost

Key insight

When you merge a and b into a + b, you pay a + b now, and that combined item keeps its size for all future merges — so every time it merges again, you pay for a and b again. Concretely, if you model the merge sequence as a binary tree whose leaves are the original items and whose internal nodes are merge results, then

$\text{total cost} = \sum_{\text{leaf } v} \text{value}(v) \cdot \text{depth}(v),$

because each original value is "paid" once per ancestor merge, and the number of ancestors equals its depth.

To minimize a sum of value × depth, the largest values must sit at the smallest depths (merged last) and the smallest values at the greatest depths (merged first). The greedy that achieves exactly this is: repeatedly merge the two smallest current items. This is the optimal-merge / Huffman-coding problem, and the greedy is provably optimal via an exchange argument: in any optimal tree the two deepest leaves are siblings, and they can be taken to be the two smallest values without increasing cost.

Algorithm

1. If there are $\le 1$ items, no merge happens — return $0$.
2. Put all items in a min-heap.
3. While more than one item remains: pop the two smallest a and b, add a + b to the running total, and push a + b back.
4. Return the running total.

Accumulating a + b at every step is what correctly charges the intermediate sums for their subsequent re-merges.

Implementation

import heapq

def minimizeSystemCost(workloads):
    if len(workloads) <= 1:
        return 0
    heap = list(workloads)
    heapq.heapify(heap)
    total = 0                      # use 64-bit accumulation (Python int is arbitrary precision)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = a + b
        total += merged            # pay for this merge; merged stays for future merges
        heapq.heappush(heap, merged)
    return total

// Java: use long for the accumulator to avoid 32-bit overflow.
long minimizeSystemCost(int[] workloads) {
    if (workloads.length <= 1) return 0L;
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int w : workloads) pq.offer((long) w);
    long total = 0L;
    while (pq.size() > 1) {
        long a = pq.poll(), b = pq.poll();
        long merged = a + b;
        total += merged;
        pq.offer(merged);
    }
    return total;
}

Complexity

• Time: $O(n \log n)$ — building the heap is $O(n)$; each of the $n - 1$ merges does a constant number of $O(\log n)$ heap operations.
• Space: $O(n)$ for the heap.

Edge cases

• Empty or single-element input → cost $0$ (no merges).
• All-equal items still work; the heap just merges them pairwise bottom-up.
• The total can be large (roughly $O(n)$ merges, each up to the full sum), so accumulate in 64-bit. In Python ints are unbounded; in Java/C++ use long.

Part 2 — Remove a contiguous block to minimize adjacent differences

Setup and decomposition

Let a = machines, n = a.length. Define the adjacent-difference array

$\text{diff}[i] = |a[i+1] - a[i]|, \quad i = 0, \dots, n-2,$

and its prefix sum P, where P[i] = diff[0] + ... + diff[i-1] (so P[0] = 0 and P[j] - P[i] is the sum of diff[i..j-1]).

Suppose we remove the block of indices s .. s+k-1. The remaining sequence is the prefix a[0..s-1] concatenated with the suffix a[s+k..n-1]. Its total adjacency cost splits into three independent pieces:

1. Prefix-internal — adjacencies fully inside a[0..s-1]: these are diff[0..s-2], summing to P[s-1] (only when s >= 1).
2. Suffix-internal — adjacencies fully inside a[s+k..n-1]: these are diff[s+k..n-2], summing to P[n-1] - P[s+k] (only when s+k <= n-1).
3. Join — exactly one new adjacency between the last kept prefix element and the first kept suffix element, $|a[s+k] - a[s-1]|$, which exists only when both sides are non-empty (s >= 1 and s+k <= n-1).

So for each candidate start s:

$\text{cost}(s) = \underbrace{P[s-1]}_{\text{if } s\ge 1} + \underbrace{\big(P[n-1] - P[s+k]\big)}_{\text{if } s+k\le n-1} + \underbrace{|a[s+k] - a[s-1]|}_{\text{if both sides non-empty}}.$

Each term is $O(1)$ given P, so sweeping all $n - k + 1$ candidate starts is $O(n)$.

Implementation

def minimizeRemainingAdjDiff(machines, k):
    a = machines
    n = len(a)
    # diff[i] = |a[i+1]-a[i]|; P[i] = sum of diff[0..i-1]
    P = [0] * n
    for i in range(1, n):
        P[i] = P[i - 1] + abs(a[i] - a[i - 1])

    best_cost = None
    best_start = 0
    for s in range(0, n - k + 1):
        right = s + k                 # first kept suffix index
        cost = 0
        if s >= 1:                    # prefix-internal adjacencies
            cost += P[s - 1]
        if right <= n - 1:            # suffix-internal adjacencies
            cost += P[n - 1] - P[right]
        if s >= 1 and right <= n - 1: # join term (both sides non-empty)
            cost += abs(a[right] - a[s - 1])
        if best_cost is None or cost < best_cost:
            best_cost = cost
            best_start = s
    return best_cost, best_start

long[] minimizeRemainingAdjDiff(int[] a, int k) {  // returns {minCost, startIndex}
    int n = a.length;
    long[] P = new long[n];                         // P[i] = sum diff[0..i-1]
    for (int i = 1; i < n; i++)
        P[i] = P[i - 1] + Math.abs((long) a[i] - a[i - 1]);

    long best = Long.MAX_VALUE;
    int bestStart = 0;
    for (int s = 0; s <= n - k; s++) {
        int right = s + k;
        long cost = 0;
        if (s >= 1) cost += P[s - 1];
        if (right <= n - 1) cost += P[n - 1] - P[right];
        if (s >= 1 && right <= n - 1) cost += Math.abs((long) a[right] - a[s - 1]);
        if (cost < best) { best = cost; bestStart = s; }
    }
    return new long[]{best, bestStart};
}

Complexity

• Time: $O(n)$ — one pass to build P, one pass over the $n - k + 1$ candidate starts, each evaluated in $O(1)$.
• Space: $O(n)$ for the prefix-sum array (reducible to $O(1)$ extra by recomputing prefix/suffix sums incrementally as s advances, but the $O(n)$ version is clearest).

Correctness check

Verified against brute force (recompute the full remaining-array cost for every s) on thousands of random arrays with negative and positive values and all valid k; the prefix/suffix/join formula matches exactly. The boundary handling is the crux: when the removed block sits at the very start (s = 0) there is no prefix and no join; when it sits at the very end (s + k = n) there is no suffix and no join.

Edge cases

• Block at either end → only one internal piece, no join term.
• k = n - 1 → exactly one element survives; cost is $0$ for whichever single element remains (no adjacencies), and any valid start that leaves one element is correct.
• Negative strengths are handled naturally because we take absolute differences; do not assume the array is sorted or positive.
• Use 64-bit accumulation: with large n and large magnitudes the summed differences can exceed 32-bit range.

Follow-up answers

• Part 1, forbidden/adjacent-only merges: If merges are restricted to adjacent items (cannot reorder), this becomes the matrix-chain-style problem solvable in $O(n^3)$ DP (or $O(n^2)$ with Knuth/Garsia–Wachs for the optimal-alphabetic-tree variant), not the simple heap greedy — the greedy is optimal only when any pair may merge. A hard "two items may never merge directly" constraint breaks the clean Huffman structure and generally requires search/DP.
• Part 1, reconstructing the merge order: Store, for each pushed sum, pointers to the two children it came from; the pop-pop-push sequence then yields the merge tree, and a post-order traversal gives a valid merge ordering.
• Part 2, maximize instead of minimize: The exact same prefix/suffix/join decomposition holds — just track the maximum of cost(s) instead of the minimum; nothing else changes.
• Part 2, "remove up to k consecutive": Extend the sweep to also consider block lengths $1..k$ (and the option of removing nothing). For a fixed length the inner evaluation is still $O(1)$, so the total becomes $O(nk)$; with a small extra structure it can stay near-linear if only the best length per start is needed.