Facebook Pixel

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

HardStackArrayMathMonotonic Stack
Leetcode Link

Problem Description

You are given an integer array nums and a positive integer k. Your task is to return the sum of the maximum and minimum elements of all subarrays with at most k elements.

Intuition

To solve this problem, we need to understand the characteristics of subarrays in terms of their maximum and minimum elements. For each element in the array, consider it as the current element of interest. Determine how it functions as the minimum or maximum in subarrays of sizes up to k:

  1. Determine the next and previous smaller elements for each element when it is considered as the minimum. This helps us understand how far to the left and right this element can extend as the minimum in a subarray.

  2. Perform a similar calculation to find the next and previous larger elements for each element when it is considered the maximum.

  3. Use these boundaries to count the number of valid subarrays where each element is the minimum or maximum. For an element positioned at index i, it contributes its value times the number of valid subarrays.

  4. Sum contributions for all elements considering them as minimum and maximum separately.

  5. Combine these results to get the total sum of maximum and minimum elements of all qualifying subarrays.

By utilizing stacks to efficiently determine the next and previous smaller/larger elements, this solution uses the concept of monotonic stacks to maintain efficiency, allow quick calculations, and ensure we are forming correct boundaries for subarrays.

Learn more about Stack, Math and Monotonic Stack patterns.

Solution Approach

To implement the solution efficiently, we utilize monotonic stacks to determine the bounds within which each element of the array can act as either the minimum or maximum in subarrays:

  1. Data Structures: Arrays prev and next are used for keeping track of the previous and next indices where a smaller or larger element occurrs, depending on whether we are considering a minimum or maximum for the subarray. Two monotonic stacks, stk, assist in populating these arrays efficiently.

  2. Population of prev and next Arrays:

    • For finding the minimum:
      • Traverse through nums, employing a stack to maintain indices of elements that form a non-decreasing sequence. If an element is smaller than the top of the stack, pop elements until this condition holds.
      • Populate prev such that it holds the index of the previous smaller element for each index.
      • Reverse traverse to fill next similarly for the right side, maintaining a non-decreasing sequence.
    • The process is similar when considering elements as maximums, with the stack maintaining a non-increasing sequence.

  3. Calculate Contributions:

    • Iterate through each element in nums, using prev and next to establish subarrays where the element at index i is the minimum or maximum.
    • Calculate how many subarrays each element can form as the minimum or maximum within the constraints:
      • Use subtraction and counting to determine valid start and end points for subarrays, considering the maximum allowed size k.

  4. Summing Contributions:

    • For each element, calculate its contribution using its value and the computed number of subarrays where it serves as the minimum or maximum.
    • Sum these contributions separately for minimum and maximum scenarios.
    • Return the combined sum of both minimum and maximum contributions for all subarrays with at most k elements.

This systematic approach ensures that we efficiently capture all necessary subarray configurations and their respective maximum and minimum values, leveraging the monotonic stack pattern to keep operations optimal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to understand the solution approach. Consider the array nums = [2, 1, 3] and k = 2. Our task is to find the sum of maximum and minimum elements for all subarrays with at most k elements.

  1. Determine Next and Previous Smaller Elements:

    • Next Smaller:

      • nums[0] = 2 → The next smaller element is nums[1] = 1.
      • nums[1] = 1 → There is no next smaller element.
      • nums[2] = 3 → There is no next smaller element.

    • Previous Smaller:

      • nums[0] = 2 → There is no previous smaller element.
      • nums[1] = 1 → There is no previous smaller element.
      • nums[2] = 3 → The previous smaller element is nums[1] = 1.

  2. Determine Next and Previous Larger Elements:

    • Next Larger:

      • nums[0] = 2 → The next larger element is nums[2] = 3.
      • nums[1] = 1 → The next larger element is nums[2] = 3.
      • nums[2] = 3 → There is no next larger element.

    • Previous Larger:

      • nums[0] = 2 → There is no previous larger element.
      • nums[1] = 1 → The previous larger element is nums[0] = 2.
      • nums[2] = 3 → There is no previous larger element.

  3. Calculate Contributions:

    For each element, we compute its contribution as a minimum and maximum:

    • Element nums[0] = 2:

      • Subarrays as minimum: [2]
      • Subarrays as maximum: [2], [2, 1]

    • Element nums[1] = 1:

      • Subarrays as minimum: [1], [2, 1], [1, 3]
      • Subarrays as maximum: [1]

    • Element nums[2] = 3:

      • Subarrays as minimum: [3]
      • Subarrays as maximum: [3], [1, 3]

  4. Summing Contributions:

    • Total Minimum Contribution:

      • From [2] (minimum is 2) = 2
      • From [1], [2, 1], [1, 3] (minimum is 1) = 1 + 1 + 1 = 3
      • From [3] (minimum is 3) = 3
      • Total = 2 + 3 + 3 = 8

    • Total Maximum Contribution:

      • From [2], [2, 1] (maximum is 2) = 2 + 2 = 4
      • From [1] (maximum is 1) = 1
      • From [3], [1, 3] (maximum is 3) = 3 + 3 = 6
      • Total = 4 + 1 + 6 = 11

  5. Final Combined Sum:

    • Total sum of maximum and minimum contributions is 8 + 11 = 19.

Thus, for the array [2, 1, 3] with k = 2, the sum of the maximum and minimum elements of all subarrays with at most k elements is 19.

Solution Implementation

1from typing import List
2
3def minMaxSubarraySum(nums: List[int], k: int) -> int:
4    """
5    Computes the sum of the minimum and maximum values of all subarrays of size k.
6
7    :param nums: A list of numbers.
8    :param k: The size of subarrays to consider.
9    :return: The sum of the minimum and maximum values across all subarrays of size k.
10    """
11
12    def computeSum(nums: List[int], k: int, isMin: bool) -> int:
13        """
14        Helper function to calculate either the min or max subarray sum using a stack method.
15
16        :param nums: A list of numbers.
17        :param k: The size of the subarrays.
18        :param isMin: A boolean flag indicating whether to calculate for min (True) or max (False).
19        :return: The calculated subarray sum.
20        """
21        n = len(nums)
22        prev = [-1] * n
23        next = [n] * n
24        stack = []
25
26        # Populate prev and next arrays for minimum or maximum calculations
27        if isMin:
28            for i in range(n):
29                while stack and nums[stack[-1]] >= nums[i]:
30                    stack.pop()
31                prev[i] = stack[-1] if stack else -1
32                stack.append(i)
33
34            stack.clear()
35
36            for i in range(n - 1, -1, -1):
37                while stack and nums[stack[-1]] > nums[i]:
38                    stack.pop()
39                next[i] = stack[-1] if stack else n
40                stack.append(i)
41        else:
42            for i in range(n):
43                while stack and nums[stack[-1]] <= nums[i]:
44                    stack.pop()
45                prev[i] = stack[-1] if stack else -1
46                stack.append(i)
47
48            stack.clear()
49
50            for i in range(n - 1, -1, -1):
51                while stack and nums[stack[-1]] < nums[i]:
52                    stack.pop()
53                next[i] = stack[-1] if stack else n
54                stack.append(i)
55
56        # Calculate the total sum based on min or max logic
57        totalSum = 0
58        for i in range(n):
59            left = prev[i]
60            right = next[i]
61            a = left + 1
62            b = i
63            d = right - 1
64
65            # Calculate sums for two ranges of the subarray
66            start1 = max(a, i - k + 1)
67            endCandidate1 = d - k + 1
68            upper1 = min(b, endCandidate1)
69
70            sum1 = 0
71            if upper1 >= start1:
72                termCount = upper1 - start1 + 1
73                first = start1
74                last = upper1
75                indexSum = (last * (last + 1)) // 2 - ((first - 1) * first) // 2
76                constantSum = (k - i) * termCount
77                sum1 = indexSum + constantSum
78
79            start2 = upper1 + 1
80            end2 = b
81            start2 = max(start2, a)
82            end2 = min(end2, b)
83
84            sum2 = 0
85            if start2 <= end2:
86                count = end2 - start2 + 1
87                term = d - i + 1
88                sum2 = term * count
89
90            totalSum += nums[i] * (sum1 + sum2)
91
92        return totalSum
93
94    minSum = computeSum(nums, k, True)
95    maxSum = computeSum(nums, k, False)
96    return minSum + maxSum
97
1import java.util.Stack;
2
3public class MinMaxSubarraySum {
4
5    /**
6     * Computes the sum of the minimum and maximum values of all subarrays of size k.
7     *
8     * @param nums - An array of numbers.
9     * @param k - The size of subarrays to consider.
10     * @return The sum of the minimum and maximum values across all subarrays of size k.
11     */
12    public static int minMaxSubarraySum(int[] nums, int k) {
13        // Compute the sum of either minimum or maximum values using a stack method
14        int minSum = computeSum(nums, k, true);
15        int maxSum = computeSum(nums, k, false);
16        return minSum + maxSum;
17    }
18
19    /**
20     * Helper function to calculate either the min or max subarray sum using a stack method.
21     *
22     * @param nums - An array of numbers.
23     * @param k - The size of the subarrays.
24     * @param isMin - A boolean flag indicating whether to calculate for min (true) or max (false).
25     * @return The calculated subarray sum.
26     */
27    private static int computeSum(int[] nums, int k, boolean isMin) {
28        int n = nums.length;
29        int[] prev = new int[n];
30        int[] next = new int[n];
31        for (int i = 0; i < n; i++) {
32            prev[i] = -1;
33            next[i] = n;
34        }
35        Stack<Integer> stack = new Stack<>();
36
37        // Populate prev and next arrays for minimum or maximum calculations
38        if (isMin) {
39            for (int i = 0; i < n; i++) {
40                while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
41                    stack.pop();
42                }
43                prev[i] = stack.isEmpty() ? -1 : stack.peek();
44                stack.push(i);
45            }
46            stack.clear();
47            for (int i = n - 1; i >= 0; i--) {
48                while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
49                    stack.pop();
50                }
51                next[i] = stack.isEmpty() ? n : stack.peek();
52                stack.push(i);
53            }
54        } else {
55            for (int i = 0; i < n; i++) {
56                while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
57                    stack.pop();
58                }
59                prev[i] = stack.isEmpty() ? -1 : stack.peek();
60                stack.push(i);
61            }
62            stack.clear();
63            for (int i = n - 1; i >= 0; i--) {
64                while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
65                    stack.pop();
66                }
67                next[i] = stack.isEmpty() ? n : stack.peek();
68                stack.push(i);
69            }
70        }
71
72        // Calculate the total sum based on min or max logic
73        int totalSum = 0;
74        for (int i = 0; i < n; i++) {
75            int left = prev[i];
76            int right = next[i];
77            int a = left + 1;
78            int b = i;
79            int c = i;
80            int d = right - 1;
81
82            // Calculate sums for two ranges of the subarray
83            int start1 = Math.max(a, i - k + 1);
84            int endCandidate1 = d - k + 1;
85            int upper1 = Math.min(b, endCandidate1);
86
87            int sum1 = 0;
88            if (upper1 >= start1) {
89                int termCount = upper1 - start1 + 1;
90                int first = start1;
91                int last = upper1;
92                int indexSum = (last * (last + 1)) / 2 - ((first - 1) * first) / 2;
93                int constantSum = (k - i) * termCount;
94                sum1 = indexSum + constantSum;
95            }
96
97            int start2 = upper1 + 1;
98            int end2 = Math.min(d, b);
99
100            int sum2 = 0;
101            if (start2 <= end2) {
102                int count = end2 - start2 + 1;
103                int term = d - i + 1;
104                sum2 = term * count;
105            }
106
107            totalSum += nums[i] * (sum1 + sum2);
108        }
109
110        return totalSum;
111    }
112
113    public static void main(String[] args) {
114        // Example usage
115        int[] nums = {1, 3, 2, 4};
116        int k = 2;
117        System.out.println(minMaxSubarraySum(nums, k));  // Output: some result
118    }
119}
120
1#include <vector>
2#include <stack>
3#include <algorithm>
4
5using namespace std;
6
7/**
8 * Computes the sum of the minimum and maximum values of all subarrays of size k.
9 *
10 * @param nums - A vector of numbers.
11 * @param k - The size of subarrays to consider.
12 * @return The sum of the minimum and maximum values across all subarrays of size k.
13 */
14int minMaxSubarraySum(const vector<int>& nums, int k) {
15    /**
16     * Helper function to calculate either the min or max subarray sum using a stack method.
17     *
18     * @param nums - A vector of numbers.
19     * @param k - The size of subarrays.
20     * @param isMin - A boolean flag indicating whether to calculate for min (true) or max (false).
21     * @return The calculated subarray sum.
22     */
23    auto computeSum = [](const vector<int>& nums, int k, bool isMin) -> long long {
24        int n = nums.size();
25        vector<int> prev(n, -1);
26        vector<int> next(n, n);
27        stack<int> s;
28
29        // Populate prev and next arrays for minimum or maximum calculations
30        if (isMin) {
31            for (int i = 0; i < n; ++i) {
32                while (!s.empty() && nums[s.top()] >= nums[i]) {
33                    s.pop();
34                }
35                prev[i] = s.empty() ? -1 : s.top();
36                s.push(i);
37            }
38            while (!s.empty()) s.pop();
39            for (int i = n - 1; i >= 0; --i) {
40                while (!s.empty() && nums[s.top()] > nums[i]) {
41                    s.pop();
42                }
43                next[i] = s.empty() ? n : s.top();
44                s.push(i);
45            }
46        } else {
47            for (int i = 0; i < n; ++i) {
48                while (!s.empty() && nums[s.top()] <= nums[i]) {
49                    s.pop();
50                }
51                prev[i] = s.empty() ? -1 : s.top();
52                s.push(i);
53            }
54            while (!s.empty()) s.pop();
55            for (int i = n - 1; i >= 0; --i) {
56                while (!s.empty() && nums[s.top()] < nums[i]) {
57                    s.pop();
58                }
59                next[i] = s.empty() ? n : s.top();
60                s.push(i);
61            }
62        }
63
64        // Calculate the total sum based on min or max logic
65        long long totalSum = 0;
66        for (int i = 0; i < n; ++i) {
67            int left = prev[i];
68            int right = next[i];
69            int a = left + 1;
70            int b = i;
71            int c = i;
72            int d = right - 1;
73
74            // Calculate sums for two ranges of the subarray
75            int start1 = max(a, i - k + 1);
76            int endCandidate1 = d - k + 1;
77            int upper1 = min(b, endCandidate1);
78
79            long long sum1 = 0;
80            if (upper1 >= start1) {
81                int termCount = upper1 - start1 + 1;
82                int first = start1;
83                int last = upper1;
84                long long indexSum = (last * (last + 1)) / 2 - ((first - 1) * first) / 2;
85                long long constantSum = (k - i) * termCount;
86                sum1 = indexSum + constantSum;
87            }
88
89            int start2 = upper1 + 1;
90            int end2 = b;
91            start2 = max(start2, a);
92            end2 = min(end2, b);
93
94            long long sum2 = 0;
95            if (start2 <= end2) {
96                int count = end2 - start2 + 1;
97                int term = d - i + 1;
98                sum2 = term * count;
99            }
100
101            totalSum += nums[i] * (sum1 + sum2);
102        }
103
104        return totalSum;
105    };
106
107    long long minSum = computeSum(nums, k, true);
108    long long maxSum = computeSum(nums, k, false);
109    return minSum + maxSum;
110}
111
1/**
2 * Computes the sum of the minimum and maximum values of all subarrays of size k.
3 *
4 * @param nums - An array of numbers.
5 * @param k - The size of subarrays to consider.
6 * @return The sum of the minimum and maximum values across all subarrays of size k.
7 */
8function minMaxSubarraySum(nums: number[], k: number): number {
9    /**
10     * Helper function to calculate either the min or max subarray sum using a stack method.
11     *
12     * @param nums - An array of numbers.
13     * @param k - The size of the subarrays.
14     * @param isMin - A boolean flag indicating whether to calculate for min (true) or max (false).
15     * @return The calculated subarray sum.
16     */
17    const computeSum = (nums: number[], k: number, isMin: boolean): number => {
18        const n = nums.length;
19        const prev: number[] = Array(n).fill(-1);
20        const next: number[] = Array(n).fill(n);
21        let stack: number[] = [];
22
23        // Populate prev and next arrays for minimum or maximum calculations
24        if (isMin) {
25            for (let i = 0; i < n; i++) {
26                while (stack.length > 0 && nums[stack[stack.length - 1]] >= nums[i]) {
27                    stack.pop();
28                }
29                prev[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
30                stack.push(i);
31            }
32            stack = [];
33            for (let i = n - 1; i >= 0; i--) {
34                while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
35                    stack.pop();
36                }
37                next[i] = stack.length > 0 ? stack[stack.length - 1] : n;
38                stack.push(i);
39            }
40        } else {
41            for (let i = 0; i < n; i++) {
42                while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) {
43                    stack.pop();
44                }
45                prev[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
46                stack.push(i);
47            }
48            stack = [];
49            for (let i = n - 1; i >= 0; i--) {
50                while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
51                    stack.pop();
52                }
53                next[i] = stack.length > 0 ? stack[stack.length - 1] : n;
54                stack.push(i);
55            }
56        }
57
58        // Calculate the total sum based on min or max logic
59        let totalSum = 0;
60        for (let i = 0; i < n; i++) {
61            const left = prev[i];
62            const right = next[i];
63            const a = left + 1;
64            const b = i;
65            const c = i;
66            const d = right - 1;
67
68            // Calculate sums for two ranges of the subarray
69            let start1 = Math.max(a, i - k + 1);
70            let endCandidate1 = d - k + 1;
71            let upper1 = Math.min(b, endCandidate1);
72
73            let sum1 = 0;
74            if (upper1 >= start1) {
75                const termCount = upper1 - start1 + 1;
76                const first = start1;
77                const last = upper1;
78                const indexSum = (last * (last + 1)) / 2 - ((first - 1) * first) / 2;
79                const constantSum = (k - i) * termCount;
80                sum1 = indexSum + constantSum;
81            }
82
83            let start2 = upper1 + 1;
84            let end2 = b;
85            start2 = Math.max(start2, a);
86            end2 = Math.min(end2, b);
87
88            let sum2 = 0;
89            if (start2 <= end2) {
90                const count = end2 - start2 + 1;
91                const term = d - i + 1;
92                sum2 = term * count;
93            }
94
95            totalSum += nums[i] * (sum1 + sum2);
96        }
97
98        return totalSum;
99    };
100
101    const minSum = computeSum(nums, k, true);
102    const maxSum = computeSum(nums, k, false);
103    return minSum + maxSum;
104}
105

Time and Space Complexity

Time Complexity

The function minMaxSubarraySum processes the nums array twice: once to calculate the minimum sum and once to calculate the maximum sum using the computeSum helper function. Analyzing the operations in computeSum:

  1. Initial Setup:
    Arrays prev and next are initialized in O(n), where n is the length of the nums array.

  2. Stack Operations for Previous and Next Calculations:

    • There are two loops that iterate over the nums array, each using a stack to determine the previous smaller or larger element's index (prev) and the next smaller or larger element’s index (next). These loops together take O(n) time because each element is pushed and popped from the stack at most once.

  3. Sum Calculation:
    After setting up prev and next, iterating again through nums to compute sums for each element also takes O(n) time.

Because these operations occur twice (once for the minimum and once for the maximum subarray sums), the time complexity for computeSum is O(n), making the overall time complexity of minMaxSubarraySum function O(n).

Space Complexity

  1. Auxiliary Space for Arrays:
    Both prev and next arrays are of length n, requiring O(n) space.

  2. Stack Space:
    The stack used in each loop has a maximum size of n, thus also consuming O(n) space.

Since auxiliary arrays and stack do not depend on any other parameter besides n, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More