287. Sum of Minimum and Maximum Elements of All Subarrays of Size K

Given an array of n integers and a window size k, consider every contiguous subarray of size k. For each such subarray add its minimum element and its maximum element; print the total of all these (min + max) sums across every window.

Input: The first line contains an integer n. The second line contains n space-separated integers (which may be negative), the array. The third line contains k, the window size. Output: Print a single integer - the total of (minimum + maximum) summed across every window of size k.

1 <= k <= n <= 10^5

You need two INDEPENDENT deques, not one - a single deque cannot simultaneously and correctly track both the running maximum and running minimum, since their required orderings (decreasing vs increasing) directly conflict.

For every fixed-size window sliding across an array, find both its smallest AND largest value, add those two together, and sum up that combined total across every window position. Brute force: For every window position, scan all k elements directly to find both the min and max - this costs O(n*k) overall, too slow for large arrays and large windows. Optimised: A MONOTONIC deque (one that only ever keeps 'still possibly winning' candidates, in strictly increasing or decreasing order) lets you find the current window's min or max in O(1) at every step, because any element that could never win against a more recent, still-in-window element is immediately discarded and never needs to be reconsidered - each element enters and leaves each deque at most once across the entire scan.

Slide a window of size k across the array one position at a time, and for each window scan all k elements inside it to find the minimum and maximum directly, adding both to a running total. This is correct by definition since it examines every element of every window, but re-scanning all k elements for every one of the roughly n windows means a lot of repeated comparison work, especially for large k. Time: O(n * k) Space: O(1)

Maintain two double-ended queues of indices: one kept in decreasing order of value (its front is always the current window's maximum) and one kept in increasing order of value (its front is always the current window's minimum). When sliding the window, pop expired indices from the back that fall outside the window, and before pushing a new index, pop from the front of each deque any values that the new element makes irrelevant (smaller values behind a new maximum, or larger values behind a new minimum). Each index is pushed and popped from each deque at most once across the whole scan, so despite the nested-looking logic, the total work is linear. Time: O(n) Space: O(k)

Maintain the current window's elements in a balanced ordered structure such as a multiset (or a self-balancing BST), inserting the incoming element and removing the outgoing element as the window slides, with each insertion or removal costing O(log k). The current minimum and maximum can then be read off the two ends of the ordered structure in O(1) per window. This avoids rescanning all k elements on every slide, cutting the per-window cost from linear to logarithmic in the window size. Time: O(n log k) Space: O(k)

1. Maintain TWO separate monotonic deques of indices as the window slides: one that always keeps track of the current window's maximum candidate, one for the minimum candidate. 2. Before adding a new index to either deque, remove any indices from its BACK whose values can never win against the new element (for the max-deque, remove anything smaller; for the min-deque, remove anything larger). 3. Before reading off an answer, remove any index from the FRONT of either deque that has slid out of the current window. 4. The front of the max-deque and the front of the min-deque directly give you that window's max and min - add them together and accumulate the running total.

Time: O(n) overall - even though there are two deques being maintained simultaneously, each array element is added to and removed from each deque at most once across the whole sliding process. Space: O(k) in the worst case, for each of the two monotonic deques.

k = n (only one window, covering the whole array); k = 1 (min equals max in every window); negative numbers in the array, as in the example; n = 10^5 for performance.

This combines TWO instances of the classic 'sliding window maximum/minimum via monotonic deque' pattern in one problem - be ready to explain each deque's invariant (max-deque strictly decreasing, min-deque strictly increasing) precisely, since mixing them up is an easy mistake under pressure.