Skip to content

3430. Maximum and Minimum Sums of at Most Size K Subarrays

Description

You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subarrays with at most k elements.

Β 

Example 1:

Input: nums = [1,2,3], k = 2

Output: 20

Explanation:

The subarrays of nums with at most 2 elements are:

Subarray Minimum Maximum Sum
[1] 1 1 2
[2] 2 2 4
[3] 3 3 6
[1, 2] 1 2 3
[2, 3] 2 3 5
Final Total Β  Β  20

The output would be 20.

Example 2:

Input: nums = [1,-3,1], k = 2

Output: -6

Explanation:

The subarrays of nums with at most 2 elements are:

Subarray Minimum Maximum Sum
[1] 1 1 2
[-3] -3 -3 -6
[1] 1 1 2
[1, -3] -3 1 -2
[-3, 1] -3 1 -2
Final Total Β  Β  -6

The output would be -6.

Β 

Constraints:

  • 1 <= nums.length <= 80000
  • 1 <= k <= nums.length
  • -106 <= nums[i] <= 106

Solutions

Solution 1: Monotonic Deques for Maximums and Minimums

The goal is to calculate total sum \(S = \sum_i (\text{MaxSum}_i + \text{MinSum}_i)\), where:

  1. \(\text{MaxSum}_i\): sum of maximum values of all valid subarrays ending at index \(i\).
  2. \(\text{MinSum}_i\): sum of minimum values of all valid subarrays ending at index \(i\).

We maintain two Deques, used as monotonic stacks with boundary control: max_stack and min_stack.

These track maximum and minimum values for all subarrays ending at index \(i\) with a length not exceeding \(k\).

Each element in deques is a triplet: [index, value, count], where count represents how many times this value acts as the max/min within current window.

Step 1: Boundary Control

For each element \(nums[i]\), check if window boundary \(\max(0, i - k + 1)\) has advanced.

  • If \(i - k \ge 0\), it means the subarray \(nums[i-k \dots i]\) would exceed length \(k\) due to inclusion of \(nums[i]\).
  • Contribution of the subarray starting at \(i-k\) must be removed. This contribution is located at the front of our deques.
  • We decrement the count of deques' front. If the front element's index falls out of window range, we popleft() to maintain efficiency.

Step 2: Monotonicity

Taking max_stack as an example:

  • While max_stack is not empty and max_stack top value \(\leq nums[i]\) (1):
    • Current \(nums[i]\) will replace this top element as the new maximum for all subarrays this top element previously "served."
    • We take over the prev_shares (which is the count) from this popped element.
    • Net increase to subarrays_max_sum is calculated as \((nums[i] - prev\_num) \times prev\_shares\).
  • After while-loop, we add \(nums[i]\)'s own contribution, as a single-element subarray, to subarrays_max_sum, and push \(nums[i]\) onto max_stack with its cumulative count and index.

Logic for min_stack processing is similar, but inequality (1) must change into min_stack top value \(\geq nums[i]\).

Step 3: Accumulation

At the end of each iteration \(i\), we add current subarrays_max_sum and subarrays_min_sum to global total subarrays_max_min_sum.

Complexity Analysis

  • Time Complexity: \(O(n)\), where \(n\) is length of \(nums\). Each element is pushed and popped at most 4 times in total among two deques.
  • Space Complexity: \(O(n)\) to store deques and state variables.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
    def minMaxSubarraySum(self, nums: list[int], k: int) -> int:
        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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    long long minMaxSubarraySum(vector<int>& nums, int k) {
        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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minMaxSubarraySum = function (nums, k) {
    const computeSum = (nums, k, isMin) => {
        const n = nums.length;
        const prev = Array(n).fill(-1);
        const next = Array(n).fill(n);
        let stk = [];

        if (isMin) {
            for (let i = 0; i < n; i++) {
                while (stk.length > 0 && nums[stk[stk.length - 1]] >= nums[i]) {
                    stk.pop();
                }
                prev[i] = stk.length > 0 ? stk[stk.length - 1] : -1;
                stk.push(i);
            }
            stk = [];
            for (let i = n - 1; i >= 0; i--) {
                while (stk.length > 0 && nums[stk[stk.length - 1]] > nums[i]) {
                    stk.pop();
                }
                next[i] = stk.length > 0 ? stk[stk.length - 1] : n;
                stk.push(i);
            }
        } else {
            for (let i = 0; i < n; i++) {
                while (stk.length > 0 && nums[stk[stk.length - 1]] <= nums[i]) {
                    stk.pop();
                }
                prev[i] = stk.length > 0 ? stk[stk.length - 1] : -1;
                stk.push(i);
            }
            stk = [];
            for (let i = n - 1; i >= 0; i--) {
                while (stk.length > 0 && nums[stk[stk.length - 1]] < nums[i]) {
                    stk.pop();
                }
                next[i] = stk.length > 0 ? stk[stk.length - 1] : n;
                stk.push(i);
            }
        }

        let totalSum = 0;
        for (let i = 0; i < n; i++) {
            const left = prev[i];
            const right = next[i];
            const a = left + 1;
            const b = i;
            const c = i;
            const d = right - 1;

            let start1 = Math.max(a, i - k + 1);
            let endCandidate1 = d - k + 1;
            let upper1 = Math.min(b, endCandidate1);

            let sum1 = 0;
            if (upper1 >= start1) {
                const termCount = upper1 - start1 + 1;
                const first = start1;
                const last = upper1;
                const indexSum = (last * (last + 1)) / 2 - ((first - 1) * first) / 2;
                const constantSum = (k - i) * termCount;
                sum1 = indexSum + constantSum;
            }

            let start2 = upper1 + 1;
            let end2 = b;
            start2 = Math.max(start2, a);
            end2 = Math.min(end2, b);

            let sum2 = 0;
            if (start2 <= end2) {
                const count = end2 - start2 + 1;
                const term = d - i + 1;
                sum2 = term * count;
            }

            totalSum += nums[i] * (sum1 + sum2);
        }

        return totalSum;
    };

    const minSum = computeSum(nums, k, true);
    const maxSum = computeSum(nums, k, false);
    return minSum + maxSum;
};

Comments