3430. Subarrays Max Min Sum

Maximum and Minimum Sums of at Most Size K Subarrays

After thinking for a bit, this problem really only tests two things:

1. Whether we're familiar with basic properties of monotonic stacks
2. Whether we can integrate a monotonic stack with other data structures

Making Traversal Logic Convenient

The task is to find maximum and minimum of every subarray of length at most $k$ for input array, and return the summation of all those maximums and minimums.

Most natural traversal approach is to let each visited index $i$ serve as subarray's right end, then look at all valid subarrays ending at $i$ to find their respective max and min.

This ensures we capture exactly the right information. Nothing more and nothing less.

Since our problem limits subarray length to at most $k$, we must control which starting indices $j$ are valid for the current right end $i$.

My habit for subarray-style problems is to let the visited index $i$ be subarray's right end, so I can look left to filter valid starting indices $j$ — whether moving, counting, summing up, or multiplying.

Biggest advantage is the traversal logic becomes genuinely convenient.

Boundary Control

When index $i$ serves as right end, first thing we do is determine which starting indices $j$ are valid:

those $j$ satisfying $\max(0, i - k + 1) \leq j \leq i$.

Once valid range for $j$ is established, the harder part follows.

Efficiently Finding Subarray Max and Min

The answer we need is $S = \Sigma_{i = 0}^{n - 1} (MaxSum_i + MinSum_i)$:

I. $MaxSum_i = \Sigma_{j = max(0, i - k + 1)}^i \max(nums[j:i + 1])$

— sum of maximum values across all valid subarrays ending at $i$.

II. $MinSum_i = \Sigma_{j = max(0, i - k + 1)}^i \min(nums[j:i + 1])$

— sum of minimum values across all valid subarrays ending at $i$.

How do we compute these two sums efficiently?

I. Starting From Default Case

Start with $MaxSum_i$ inheriting the value of $MaxSum_{i - 1}$, then make two adjustments:

Always happens: add $nums[i]$ for its contribution as a maximum, as there's now a single-element subarray $nums[i]$.

Conditional: if $i - k + 1 > 0$, subtract the max value of subarrays containing $nums[i - k]$.

The subarray $nums[i - k:i]$ of length $k$ was valid when subarray's right end was $i - 1$.

Now that $nums[i]$ enters, the leftmost element $nums[i - k]$ must retire to let subarray length stay at $k$.

This is why we do boundary control. After these adjustments, scan for any further corrections.

II. Incremental Comparison: Responsibilities Transitions

Every valid subarray ending at $i$ contains $nums[i]$.

So if $nums[i] \geq nums[i - 1]$ (1), none of these subarrays can have $nums[i - 1]$ as their maximum.

Why include equality? We traverse left to right, if two adjacent elements are equal, definitely prefer the newer one: it arrived later so it can stay longer 😁

In this case, $nums[i - 1]$ was the maximum for $l$ times of all valid subarrays ending at $i - 1$.

Those $l$ times are now fully transferred to $nums[i]$, producing a net increase of

$(nums[i] - nums[i - 1]) \times l$ added to $MaxSum_i$.

Since $nums[i]$ unseated $nums[i - 1]$, it must also compare against $nums[i - 2], \ldots, nums[max(0, i - k + 1)]$.

When do we stop? When we hit the first $nums[j]$ that is greater than $nums[i]$.

Everything to the left of $nums[j]$ is even larger, so $nums[i]$ can't beat them.

Isn't this a monotonic decreasing stack approach?

Pop all elements that aren't greater than $nums[i]$, collect their transferred shares, and push $nums[i]$ into stack.

Since $MaxSum_i$ can be tracked in real time using a monotonic decreasing stack, $MinSum_i$ can naturally be handled with a monotonic increasing stack.

Only difference: transfer condition flips. For monotonic increasing stack, $nums[i] \leq nums[i - 1]$ triggers handoff (2),

Which is the opposite inequality compared to (1) for $MaxSum_i$.

III. Monotonic Stack Meets Queue

As mentioned, every iteration enforces boundary control. Have to discard max/min contributions from subarrays that are no longer in current valid range.

Such a removal is FIFO, so we merge queue and monotonic stack into a deque that supports both FIFO and LIFO.

Each element on stack is a tuple of (Index, Number, Shares), each field is a critical role:

I. Index: we need to know where the max/min element is located.

This allows boundary control to determine when it falls out of current window and must retire.

II. Number: numerical value of the max or min is needed, since both stacks are always comparing against newly visited element.

III. Shares: among all valid subarrays ending at the current index, the contribution count of an element serving as the max (in decreasing stack) or min (for increasing stack).

Which is actually the $l$ from our handoff explanation above. It's what allows $MaxSum_i$ and $MinSum_i$ to correctly adjust.

Think of it like bonuses: issued upfront at an estimated amount, then corrected at the end based on actual performance.

Each element enters both stacks exactly once for each. Every element leaves two stacks at most twice in total. Time and space complexity: $O(n)$.

C++

#include <deque>
#include <vector>
using namespace std;

long long computeMaxMinSum(vector<int>& nums, int k) //  LeetCode Q.3430.
{
    long long totalMaxMinSum = 0;
    long long windowMaxSum = 0, windowMinSum = 0;

    // Format: {idx, num, shares}. Use long long to prevent overflow.
    deque<tuple<int, int, long long>> maxStack, minStack;

    for (int endIdx = 0; endIdx < nums.size(); endIdx++) {
        int startIdx = max(0, endIdx - k + 1);

        // Window start idx slides by 1: must update stacks' info.
        if (startIdx > 0) {
            get<2>(maxStack.front())--; // Decrement stack's front num shares.
            windowMaxSum -= get<1>(maxStack.front());

            // Front num out of window.
            if (get<0>(maxStack.front()) < startIdx)
                maxStack.pop_front();

            get<2>(minStack.front())--; // Decrement stack's front num shares.
            windowMinSum -= get<1>(minStack.front());

            // Front num out of window.
            if (get<0>(minStack.front()) < startIdx)
                minStack.pop_front();
        }

        long long num = nums[endIdx];

        long long maxShares = 1; // Base case.
        windowMaxSum += num;

        while (!maxStack.empty() && get<1>(maxStack.back()) <= num) {
            int prevNum = get<1>(maxStack.back());
            long long prevShares = get<2>(maxStack.back());
            maxStack.pop_back();

            maxShares += prevShares; // Max shares transition.

            // Reflect transition in max sum.
            windowMaxSum += (num - prevNum) * prevShares;
        }

        maxStack.push_back({endIdx, num, maxShares});

        long long minShares = 1; // Base case.
        windowMinSum += num;

        while (!minStack.empty() && get<1>(minStack.back()) >= num) {
            int prevNum = get<1>(minStack.back());
            long long prevShares = get<2>(minStack.back());
            minStack.pop_back();

            minShares += prevShares; // Min shares transition.

            // Reflect transition in min sum.
            windowMinSum += (num - prevNum) * prevShares;
        }

        minStack.push_back({endIdx, num, minShares});

        totalMaxMinSum += windowMaxSum + windowMinSum;
    }

    return totalMaxMinSum;
}

Python

from collections import deque


def compute_max_min_sum(nums: list[int], k: int) -> int:  # LeetCode Q.3430.
    subarrays_max_min_sum = 0

    max_stack: deque[list[int]] = deque([])  # Format: [idx, num, shares].
    subarrays_max_sum = 0

    min_stack: deque[list[int]] = deque([])  # Format: [idx, num, shares].
    subarrays_min_sum = 0

    for end_idx, num in enumerate(nums):
        start_idx = max(0, end_idx - k + 1)

        # Window start idx slides by 1: must update stacks' info.
        if start_idx > 0:
            max_stack[0][2] -= 1  # Decrement stack's front num shares.
            subarrays_max_sum -= max_stack[0][1]

            if max_stack[0][0] < start_idx:  # Front num out of window.
                max_stack.popleft()

            min_stack[0][2] -= 1  # Decrement stack's front num shares.
            subarrays_min_sum -= min_stack[0][1]

            if min_stack[0][0] < start_idx:  # Front num out of window.
                min_stack.popleft()

        max_shares = 1  # Base case.
        subarrays_max_sum += num

        while max_stack and max_stack[-1][1] <= num:
            _, prev_num, prev_shares = max_stack.pop()

            max_shares += prev_shares  # Max shares transition.

            # Reflect transition in max sum.
            subarrays_max_sum += (num - prev_num) * prev_shares

        max_stack.append([end_idx, num, max_shares])

        min_shares = 1  # Base case.
        subarrays_min_sum += num

        while min_stack and min_stack[-1][1] >= num:
            _, prev_num, prev_shares = min_stack.pop()

            min_shares += prev_shares  # Min shares transition.

            # Reflect transition in min sum.
            subarrays_min_sum += (num - prev_num) * prev_shares

        min_stack.append([end_idx, num, min_shares])

        subarrays_max_min_sum += subarrays_max_sum + subarrays_min_sum

    return subarrays_max_min_sum