Inverse Window (Pick from the Ends)

Some problems say: each turn, take an item from the left end or the right end, and minimize or maximize something. It looks like a choice tree, or DP over "take left / take right", but it's usually a sliding window in disguise. Whatever you take from the two ends, what you leave behind is one contiguous block in the middle. So you window over that block instead.

The idea#

Taking i items from the left and j from the right leaves the middle nums[i : n - j]. So every valid "take from the ends" plan matches exactly one contiguous middle window, and back again. That lets you flip the question:

Original question	Inverse question
Take exactly `k` items from the ends, maximize their sum	Keep a middle window of size `n - k`, minimize its sum
Take from the ends until they sum to `x`, minimize the count	Keep the longest middle window with sum `total - x`

You then read the answer from total - window or n - window_length. You never track the picks themselves: everything outside the window is the part you took.

How to spot it#

The question lets you take only from the two ends. Look for these signals.

"Each step, remove the leftmost or rightmost element."
"Pick k cards from the beginning or end of the row."
Choose-or-skip from both ends suggests DP, but the constraints (around $10^5$ ) are too large for an $O(n^2)$ table.
The thing you take is "two prefixes glued together", which means the thing you keep is one subarray.

Template#

First turn the question about the ends into a question about the middle. Then run a normal window, fixed or variable, over the middle.

total = sum of all items
target = what the kept middle must satisfy   # e.g. total - x
if no middle can satisfy target: return "impossible"
best_middle = none
for each window over the middle:           # fixed or variable shape
    if window meets target:
        best_middle = better of best_middle and window
if best_middle is none: return "impossible"
return answer from what is outside best_middle
                                         # total - sum or n - length

The middle is one subarray, so each pointer moves at most n times. The scan is $O(n)$ .

Pitfalls#

The window code is standard, so the mistakes here come from the flip itself.

Missing the impossible case. If the target for the middle can't be met even by the empty or the whole window, no plan works. Check before the loop.
Minimize vs maximize flips. Maximizing what you take means minimizing the window when the total is fixed. Maximizing the count you keep means minimizing the operations.
The empty middle. Taking everything leaves an empty window. Make sure your loop can count it.
Negative numbers. The shrink-while-too-big loop only works when every value is positive. With negatives, use a prefix-sum hashmap to find the longest subarray with a given sum (see Prefix Sum + Hashmap).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Maximum Points You Can Obtain from Cards

You take exactly k cards, so the kept middle always has n - k cards. Slide a fixed-size window of n - k and track its smallest sum. The answer is total - min_window_sum. If k == n, the window is empty and the answer is total.

Hint: Minimum Operations to Reduce X to Zero

Find the longest middle window with sum target = total - x, then answer n - longest. All values are positive, so shrink while window > target and record when window == target.

Hint: Minimum Operations to Reduce X to Zero: edge cases

If target < 0, x is bigger than the whole array's sum, so return -1 early. When target == 0, the empty window counts and the answer is n (take everything). If no window ever hits the target, return -1.

Key takeaways#

Taking from both ends always leaves one contiguous middle block.
Window over what you keep; read the answer from what's outside it.
A fixed number of picks means a fixed-size middle window.
"Choose left or right" smells like DP, but check for the inverse window first.

Core idea#

When you must take items from the left or right end, the part you leave is one contiguous middle block. Slide a window over that block instead.

Key points#

Taking i from the left and j from the right leaves nums[i : n - j].
Every "take from the ends" plan matches exactly one middle window.
Read the answer from total - window or n - window_length.
A fixed number of picks means a fixed-size middle window of n - k.
"Choose left or right" looks like DP. Check for the inverse window first.
Spot it: "remove the leftmost or rightmost element", "pick k cards from the ends", constraints near $10^5$ .

Flip the question#

Original question	Inverse question
Take exactly `k` cards, maximize their sum	Keep a window of size `n - k`, minimize its sum
Take until the sum is `x`, minimize the count	Keep the longest window with sum `total - x`

Template#

total = sum of all items
target = what the kept middle must satisfy   # e.g. total - x
if no middle can satisfy target: return "impossible"
best_middle = none
for each window over the middle:             # fixed or variable
    if window meets target:
        best_middle = better of best_middle and window
return answer from outside best_middle       # total - sum, n - length

Pitfalls#

Missing target < 0. If x is bigger than the total, no plan works.
Mixing up the direction. Maximizing what you take means minimizing the window.
Negative numbers. The shrink loop needs all values positive. Use a prefix-sum hashmap instead.
k == n in the cards problem. The window is empty and the answer is total.

Say it in an interview#

"Whatever you take from the two ends, you keep one contiguous middle block."
"So window over what you keep and read the answer from what is outside it."