Prefix-Suffix Sweeps

From Running Min/Max to Running Heaps

In Lesson 1, our prefix and suffix arrays tracked a single value: a running minimum or maximum. That works when you need the best one element from each side.

But what if each side needs the best \(N\) elements? A single min() call cannot maintain the top-\(N\). You need a heap.

This lesson upgrades the decoupled sweep: the prefix and suffix arrays are built with heaps instead of simple comparisons. The three-phase structure (build prefix, build suffix, sweep split) stays identical. If you internalized Lesson 1, the only new thing here is the data structure inside each pass.

Prefix-best and suffix-best arrays on a number line showing the valid sweep range

The diagram shows how maxLeftSum[i] increases as the heap has more elements to choose from (moving right), while minRightSum[i] decreases as it has more elements to choose from (moving left). The valid sweep range — where both sides have at least \(N\) elements — is the window \([N-1, 2N-1]\).

ARC 074D — 3N Numbers

Problem. You are given \(3N\) numbers in a row: \(a[0], a[1], \ldots, a[3N-1]\). Choose \(N\) numbers from the first part (call them Set A) and \(N\) numbers from the rest (call them Set B). The split point determines what counts as "first part" vs "rest." Maximize \(\text{Sum}(A) - \text{Sum}(B)\).

More precisely: choose a split index \(i\) (where \(N-1 \leq i \leq 2N-1\)). Pick \(N\) elements from \(a[0..i]\) to maximize their sum. Pick \(N\) elements from \(a[i+1..3N-1]\) to minimize their sum. The answer is:

\[\max_{i \in [N-1,\; 2N-1]} \left( \text{maxLeftSum}[i] - \text{minRightSum}[i+1] \right)\]

The Greedy Choice: Sweep a split point. Use a min-heap to track the \(N\) largest elements from the left, and a max-heap to track the \(N\) smallest from the right.

Why Those Bounds?

The split range \(N-1 \leq i \leq 2N-1\) comes from a hard constraint on both sides:

Left side needs at least \(N\) elements. The left portion is \(a[0..i]\), which has \(i+1\) elements. We need \(i + 1 \geq N\), so \(i \geq N - 1\). The earliest valid split is index \(N - 1\).
Right side needs at least \(N\) elements. The right portion is \(a[i+1..3N-1]\), which has \(3N - i - 1\) elements. We need \(3N - i - 1 \geq N\), so \(i \leq 2N - 1\). The latest valid split is index \(2N - 1\).

If you forget these bounds, your code will try to select \(N\) elements from a set smaller than \(N\) and crash or produce garbage.

The Trap

If you sort the entire array and take the \(N\) largest for A and \(N\) smallest for B, you ignore the positional constraint: elements in A must come from the left portion, elements in B must come from the right portion. Sorting destroys position information.

Concrete failure: array \(= [1, 9, 1, 9, 1, 9]\) with \(N=2\). Sorting gives \([1,1,1,9,9,9]\). Taking the 2 largest (9,9) and 2 smallest (1,1) gives difference 16. But with split at \(i=2\), left is \([1,9,1]\), right is \([9,1,9]\). Best 2 from left: \(9+1=10\). Smallest 2 from right: \(9+1=10\). Difference: 0. The sort-based answer of 16 is a lie.

The Fix: Two Heap Sweeps

Pass 1 — maxLeftSum (left to right with min-heap).

Scan \(i = 0, 1, \ldots, 3N-1\). Maintain a min-heap of size \(N\) holding the \(N\) largest elements seen so far. Track their sum.

Add \(a[i]\) to the heap and to currentLeftSum.
If heap size exceeds \(N\), pop the smallest element and subtract it from currentLeftSum.
Record maxLeftSum[i] = currentLeftSum.

Why a min-heap? We keep the \(N\) largest. The min-heap surfaces the weakest member. When a stronger element arrives, the weakest gets ejected. Think of it as a club with \(N\) spots — whenever someone better shows up, the weakest member gets bounced.

Pass 2 — minRightSum (right to left with max-heap).

Scan \(i = 3N-1, 3N-2, \ldots, 0\). Maintain a max-heap of size \(N\) holding the \(N\) smallest elements seen so far. Track their sum.

Add \(a[i]\) to the heap and to currentRightSum.
If heap size exceeds \(N\), pop the largest element and subtract it from currentRightSum.
Record minRightSum[i] = currentRightSum.

Why a max-heap? We keep the \(N\) smallest. The max-heap surfaces the largest of our chosen \(N\). Same bouncer logic, inverted.

Pass 3 — Sweep the split point. For each \(i\) in \([N-1, 2N-1]\), combine maxLeftSum[i] and minRightSum[i+1]. Take the max.

Full State Trace

Let's pause and track exactly what the heaps are doing at each step.

Input: \(N = 2\), array \(= [3, 1, 4, 1, 5, 9]\) (\(3N = 6\) elements).

Pass 1 — maxLeftSum (max sum of 2 elements from left):

\(i\)	\(a[i]\)	Heap (min-heap)	Action	currentLeftSum	maxLeftSum[\(i\)]
0	3	{3}	Add 3, size \(< N\)	3	3
1	1	{1, 3}	Add 1, size \(= N\), keep both	4	4
2	4	{3, 4}	Add 4, size \(> N\), eject 1 (smallest)	7	7
3	1	{3, 4}	Add 1, size \(> N\), eject 1 (just entered)	7	7
4	5	{4, 5}	Add 5, size \(> N\), eject 3	9	9
5	9	{5, 9}	Add 9, size \(> N\), eject 4	14	14

Pass 2 — minRightSum (min sum of 2 elements from right):

\(i\)	\(a[i]\)	Heap (max-heap)	Action	currentRightSum	minRightSum[\(i\)]
5	9	{9}	Add 9, size \(< N\)	9	9
4	5	{9, 5}	Add 5, size \(= N\), keep both	14	14
3	1	{5, 1}	Add 1, size \(> N\), eject 9 (largest)	6	6
2	4	{4, 1}	Add 4, size \(> N\), eject 5	5	5
1	1	{1, 1}	Add 1, size \(> N\), eject 4	2	2
0	3	{1, 1}	Add 3, size \(> N\), eject 3	2	2

Pass 3 — Sweep (valid split points \(i = 1\) to \(3\), both timelines merged):

Split \(i\)	maxLeftSum[\(i\)]	minRightSum[\(i+1\)]	Difference
1	4	5	-1
2	7	6	1
3	7	14	-7

Answer: 1 (split at \(i=2\): pick \(\{3, 4\}\) from left, sum=7; pick \(\{1, 1\}\) from right, sum=6; difference=1).

Manual Verification

With split at \(i=2\), the left portion is \([3, 1, 4]\) and right is \([1, 5, 9]\). Best 2 from left: \(3+4=7\). Smallest 2 from right: \(1+5=6\). Difference: \(7-6=1\). Correct.

Try It

At split \(i=3\), why is the difference \(-7\)? The left portion is \([3,1,4,1]\) — the best 2 sum to 7. The right portion is \([5,9]\) — the only 2 elements sum to 14. So the difference is \(7-14 = -7\). Worse than splitting earlier. The sweep finds this automatically.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numRequired;
    cin >> numRequired;
    int totalElements = 3 * numRequired;

    vector<long long> elements(totalElements);
    for (int i = 0; i < totalElements; i++) {
        cin >> elements[i];
    }

    vector<long long> maxLeftSum(totalElements);
    auto minHeapCompare = [](long long a, long long b) {
        return a > b;
    };
    priority_queue<long long, vector<long long>, decltype(minHeapCompare)> leftMinHeap(minHeapCompare);
    long long currentLeftSum = 0;

    for (int i = 0; i < totalElements; i++) {
        currentLeftSum += elements[i];
        leftMinHeap.push(elements[i]);
        if ((int)leftMinHeap.size() > numRequired) {
            currentLeftSum -= leftMinHeap.top();
            leftMinHeap.pop();
        }
        maxLeftSum[i] = currentLeftSum;
    }

    vector<long long> minRightSum(totalElements);
    auto maxHeapCompare = [](long long a, long long b) {
        return a < b;
    };
    priority_queue<long long, vector<long long>, decltype(maxHeapCompare)> rightMaxHeap(maxHeapCompare);
    long long currentRightSum = 0;

    for (int i = totalElements - 1; i >= 0; i--) {
        currentRightSum += elements[i];
        rightMaxHeap.push(elements[i]);
        if ((int)rightMaxHeap.size() > numRequired) {
            currentRightSum -= rightMaxHeap.top();
            rightMaxHeap.pop();
        }
        minRightSum[i] = currentRightSum;
    }

    long long maxDifference = -2e18;
    for (int i = numRequired - 1; i < 2 * numRequired; i++) {
        maxDifference = max(maxDifference, maxLeftSum[i] - minRightSum[i + 1]);
    }

    cout << maxDifference << "\n";
    return 0;
}

Complexity: \(O(N \log N)\) for the heap operations across \(3N\) elements. Space: \(O(N)\) for the heaps plus \(O(N)\) for the arrays.

Contrast Problem: Minimize the Heights (No Heaps Needed)

This problem uses the same decoupled sweep structure, but each pass is \(O(1)\) per step instead of \(O(\log N)\). Recognizing when you don't need a heap is just as important as knowing when you do.

Problem. \(N\) towers with heights \(h[0], h[1], \ldots, h[n-1]\). You must add or subtract exactly \(K\) from each tower's height (you choose independently per tower). Minimize the difference between the tallest and shortest tower after modification.

Why No Heaps?

In 3N Numbers, each side selects the best \(N\) out of many elements — that's a top-\(K\) problem requiring a heap. In Tower Heights, each side contributes a single extreme: the tallest tower after modification, and the shortest. A single max() or min() suffices. No heap needed.

This is the diagnostic: if each side of the split contributes one value, use a running min/max. If each side contributes the best \(K\) values, use a heap.

Reduction to a Sweep

After modification, each tower has height \(h[i] + K\) or \(h[i] - K\). Sort the towers by original height.

Key observation. In the optimal solution, there exists a split point \(s\) such that towers \(0..s\) are raised (\(h[i] + K\)) and towers \(s+1..n-1\) are lowered (\(h[i] - K\)). Why? If a shorter tower is lowered and a taller tower is raised, swapping their choices can only help. So the raised set is a prefix and the lowered set is a suffix — an exchange argument.

For a given split point \(s\): - Maximum height \(= \max(h[s] + K,\; h[n-1] - K)\) - Minimum height \(= \min(h[0] + K,\; h[s+1] - K)\) - Spread \(=\) Maximum \(-\) Minimum

Sweep \(s\) from 0 to \(n-2\), track the minimum spread.

Full State Trace

Heights: \([1, 5, 8, 10]\), \(K = 2\). Sorted: \([1, 5, 8, 10]\).

Base spread (no modification helps): \(10 - 1 = 9\).

Split \(s\)	\(h[s]+K\)	\(h[n-1]-K\)	hi	\(h[0]+K\)	\(h[s+1]-K\)	lo	Spread
0	3	8	8	3	3	3	5
1	7	8	8	3	6	3	5
2	10	8	10	3	8	3	7

Answer: 5 (raise towers 1 and 5, lower towers 8 and 10 → heights \([3, 7, 6, 8]\), spread \(= 8 - 3 = 5\)).

Code

int minimizeHeights(vector<int>& towerHeights, int adjustment) {
    int numTowers = towerHeights.size();
    auto ascendingCompare = [](int a, int b) {
        return a < b;
    };
    sort(towerHeights.begin(), towerHeights.end(), ascendingCompare);

    int minSpread = towerHeights[numTowers - 1] - towerHeights[0];

    for (int i = 0; i < numTowers - 1; i++) {
        int highestPotential = max(towerHeights[i] + adjustment, towerHeights[numTowers - 1] - adjustment);
        int lowestPotential = min(towerHeights[0] + adjustment, towerHeights[i + 1] - adjustment);
        if (lowestPotential < 0) continue;
        minSpread = min(minSpread, highestPotential - lowestPotential);
    }

    return minSpread;
}

Try It

What happens with heights \([1, 2, 3]\) and \(K = 3\)? After sorting, split \(s=0\): raised \(= [4]\), lowered \(= [2-3, 3-3] = [-1, 0]\). But heights must be non-negative — the continue guard kicks in. Work through all split points and verify that only \(s=2\) (or no valid \(s\)) produces a valid answer.

Comparing the Two Problems

Aspect	3N Numbers	Tower Heights
Prefix structure	Heap (top-\(N\) sum)	Constant (\(h[s]+K\) and \(h[0]+K\))
Suffix structure	Heap (bottom-\(N\) sum)	Constant (\(h[n-1]-K\) and \(h[s+1]-K\))
Sweep variable	Split index	Split index
Per-step cost	\(O(\log N)\) for heap	\(O(1)\)
Total	\(O(N \log N)\)	\(O(N \log N)\) for sort, \(O(N)\) for sweep

The shape is the same. The complexity of each prefix/suffix step varies, but the three-phase architecture is unchanged. The diagnostic: count how many elements each side contributes. One element → running min/max. \(K\) elements → heap.

When to Use Heap Sweeps vs Simple Sweeps

Simple sweep (running min/max): when each side of the split contributes a single extreme value.
Heap sweep: when each side of the split contributes the best \(K\) elements, and \(K > 1\). The heap maintains the top-\(K\) (or bottom-\(K\)) incrementally as the split point moves.
DP sweep (next lesson): when the contribution from each side depends on structure beyond just "pick the best \(K\) elements" — e.g., contiguous segments with internal constraints.

Challenge

Suppose you have \(4N\) numbers and need to choose \(N\) from the first quarter and \(N\) from the last quarter to maximize the difference. How many heaps do you need? What are the valid sweep bounds? Sketch the solution before coding it.

Problems

Problem	Link	Difficulty
ARC 074D — 3N Numbers	atcoder.jp/contests/arc074/tasks/arc074_b	Medium
Minimize the Heights	GeeksforGeeks	Medium
LeetCode 123 — Buy and Sell Stock III	leetcode.com/problems/best-time-to-buy-and-sell-stock-iii	Hard