Facebook Pixel

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

HardStackArrayMathMonotonic Stack
Leetcode Link

Problem Description

Given an integer array nums and a positive integer k, you need to find the sum of the maximum and minimum elements across all possible subarrays that have at most k elements.

A subarray is a contiguous portion of the array. For each valid subarray with length between 1 and k, you need to:

  1. Find the minimum element in that subarray
  2. Find the maximum element in that subarray
  3. Add both values to a running total

The final answer is the sum of all these minimum and maximum values across all valid subarrays.

For example, if nums = [1, 2, 3] and k = 2:

  • Subarrays of length 1: [1], [2], [3]
    • Min values: 1, 2, 3 (sum = 6)
    • Max values: 1, 2, 3 (sum = 6)
  • Subarrays of length 2: [1,2], [2,3]
    • Min values: 1, 2 (sum = 3)
    • Max values: 2, 3 (sum = 5)
  • Total sum = 6 + 6 + 3 + 5 = 20

The solution uses a monotonic stack approach to efficiently calculate the contribution of each element as a minimum or maximum across all valid subarrays. For each element at index i, it finds:

  • The range where this element is the minimum (or maximum)
  • Counts how many valid subarrays (with length ≤ k) include this element as their minimum (or maximum)
  • Multiplies the element value by this count to get its total contribution
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The naive approach would be to enumerate all possible subarrays with length at most k, then find the minimum and maximum for each subarray. However, this would be inefficient with time complexity of O(n²k).

The key insight is to think about the problem from a different angle: instead of looking at each subarray individually, we can consider the contribution of each element. For each element in the array, we ask:

  • In how many valid subarrays (length ≤ k) does this element serve as the minimum?
  • In how many valid subarrays (length ≤ k) does this element serve as the maximum?

If we can count these occurrences efficiently, we can calculate the total contribution of each element by multiplying its value by the count.

To find where an element acts as the minimum or maximum, we need to identify its "dominance range" - the largest range where it remains the minimum (or maximum). For element at index i:

  • Find prev[i]: the nearest index to the left where an element is smaller (for minimum) or larger (for maximum)
  • Find next[i]: the nearest index to the right where an element is smaller/equal (for minimum) or larger/equal (for maximum)
  • The range (prev[i], next[i]) is where element i dominates

This range finding can be done efficiently using a monotonic stack in O(n) time.

Once we have the dominance range for each element, we need to count valid subarrays within this range that:

  1. Include the element at index i
  2. Have length at most k

The counting involves careful consideration of the subarray boundaries. For each starting position j in the valid range, we determine how many ending positions create subarrays of length ≤ k that include index i. This gives us a mathematical formula to compute the contribution without explicitly iterating through all subarrays.

By computing the sum of minimum contributions and maximum contributions separately, then adding them together, we get the final answer in O(n) time complexity.

Learn more about Stack, Math and Monotonic Stack patterns.

Solution Approach

The solution implements a contribution-based approach using monotonic stacks to efficiently calculate the sum of minimum and maximum elements across all valid subarrays.

Main Structure: The solution uses a helper function computeSum(nums, k, isMin) that calculates either the sum of all minimum elements (when isMin = true) or maximum elements (when isMin = false) across all valid subarrays.

Step 1: Build Dominance Ranges Using Monotonic Stacks

For each element at index i, we find:

  • prev[i]: The rightmost index less than i where the element is strictly smaller (for min) or strictly larger (for max)
  • next[i]: The leftmost index greater than i where the element is smaller or equal (for min) or larger or equal (for max)
// For minimum calculation
while (stk.length > 0 && nums[stk[stk.length - 1]] >= nums[i]) {
    stk.pop();
}
prev[i] = stk.length > 0 ? stk[stk.length - 1] : -1;

The monotonic stack maintains indices in increasing order of values for minimum calculation, and decreasing order for maximum calculation.

Step 2: Count Valid Subarrays for Each Element

For element at index i with dominance range (prev[i], next[i]):

  • Define boundaries: a = prev[i] + 1, b = i, c = i, d = next[i] - 1
  • Valid subarrays must:
    • Start in range [a, b]
    • End in range [c, d]
    • Have length at most k

The counting is split into two parts:

Part 1: Variable-length contribution

  • Starting positions: start1 = max(a, i - k + 1) to upper1 = min(b, d - k + 1)
  • For each starting position j in this range, the number of valid ending positions is (j + k - 1) - i + 1 = j + k - i
  • Total contribution: sum1 = Σ(j + k - i) for j from start1 to upper1
  • This simplifies to: indexSum + constantSum where:
    • indexSum = (upper1 * (upper1 + 1))/2 - ((start1 - 1) * start1)/2
    • constantSum = (k - i) * termCount

Part 2: Fixed-length contribution

  • Starting positions: start2 = max(upper1 + 1, a) to end2 = min(b, b)
  • For these positions, all subarrays extend to the maximum possible ending d
  • Each contributes: d - i + 1 valid subarrays
  • Total: sum2 = (d - i + 1) * count

Step 3: Calculate Total Contribution

For each element nums[i], its total contribution is:

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

Step 4: Combine Results

The final answer is the sum of minimum and maximum contributions:

return minSum + maxSum

Time Complexity: O(n) - Each element is pushed and popped from the stack at most once, and the contribution calculation is O(1) per element.

Space Complexity: O(n) - For the prev, next arrays and the stack.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a small example with nums = [2, 1, 3] and k = 2.

Step 1: Calculate Minimum Sum Contribution

First, we find the dominance ranges for each element as a minimum using a monotonic increasing stack:

For index 0 (value=2):

  • Stack is empty, so prev[0] = -1
  • Looking forward: 1 < 2, so next[0] = 1
  • Dominance range: (-1, 1)

For index 1 (value=1):

  • Stack has [0], but nums[0]=2 >= 1, so pop. Stack empty, prev[1] = -1
  • Looking forward: 3 > 1, so next[1] = 3 (end of array)
  • Dominance range: (-1, 3)

For index 2 (value=3):

  • Stack has [1], nums[1]=1 < 3, so prev[2] = 1
  • Looking forward: end of array, so next[2] = 3
  • Dominance range: (1, 3)

Now count valid subarrays where each element is the minimum:

Index 0 (value=2):

  • Range boundaries: a=0, b=0, c=0, d=0
  • Valid subarrays must start at 0 and end at 0
  • Only subarray: [2] with length 1 ≤ k=2 ✓
  • Contribution: 2 × 1 = 2

Index 1 (value=1):

  • Range boundaries: a=0, b=1, c=1, d=2
  • Valid subarrays containing index 1:
    • Start at 0: [0,1] (length 2 ✓), [0,1,2] (length 3 > k ✗)
    • Start at 1: [1] (length 1 ✓), [1,2] (length 2 ✓)
  • Count = 3 subarrays
  • Contribution: 1 × 3 = 3

Index 2 (value=3):

  • Range boundaries: a=2, b=2, c=2, d=2
  • Only subarray: [3] with length 1 ≤ k=2 ✓
  • Contribution: 3 × 1 = 3

Minimum sum = 2 + 3 + 3 = 8

Step 2: Calculate Maximum Sum Contribution

Find dominance ranges for each element as a maximum using a monotonic decreasing stack:

For index 0 (value=2):

  • Stack empty, prev[0] = -1
  • Looking forward: 1 < 2, continues to 3 > 2, so next[0] = 2
  • Dominance range: (-1, 2)

For index 1 (value=1):

  • Stack has [0], nums[0]=2 > 1, so prev[1] = 0
  • Looking forward: 3 > 1, so next[1] = 2
  • Dominance range: (0, 2)

For index 2 (value=3):

  • Stack has [0,1], but nums[1]=1 < 3 and nums[0]=2 < 3, pop both
  • Stack empty, prev[2] = -1
  • End of array, next[2] = 3
  • Dominance range: (-1, 3)

Count valid subarrays where each element is the maximum:

Index 0 (value=2):

  • Range boundaries: a=0, b=0, c=0, d=1
  • Valid subarrays:
    • [2] (start=0, end=0, length=1 ✓)
    • [2,1] (start=0, end=1, length=2 ✓)
  • Contribution: 2 × 2 = 4

Index 1 (value=1):

  • Range boundaries: a=1, b=1, c=1, d=1
  • Only subarray: [1] with length 1 ✓
  • Contribution: 1 × 1 = 1

Index 2 (value=3):

  • Range boundaries: a=0, b=2, c=2, d=2
  • Valid subarrays ending at index 2:
    • Start at 1: [1,3] (length 2 ✓)
    • Start at 2: [3] (length 1 ✓)
  • Contribution: 3 × 2 = 6

Maximum sum = 4 + 1 + 6 = 11

Final Answer: 8 + 11 = 19

We can verify this by listing all subarrays:

  • [2]: min=2, max=2
  • [1]: min=1, max=1
  • [3]: min=3, max=3
  • [2,1]: min=1, max=2
  • [1,3]: min=1, max=3

Sum = (2+2) + (1+1) + (3+3) + (1+2) + (1+3) = 19 ✓

Solution Implementation

1def minMaxSubarraySum(nums, k):
2    """
3    Calculates the sum of minimum and maximum values across all subarrays of length k
4  
5    Args:
6        nums: The input array of numbers
7        k: The length of subarrays to consider
8  
9    Returns:
10        The sum of all minimum values plus the sum of all maximum values
11    """
12  
13    def compute_sum(nums, k, is_min):
14        """
15        Computes the sum contribution of either minimum or maximum elements
16        across all subarrays of length k
17      
18        Args:
19            nums: The input array
20            k: The subarray length
21            is_min: Whether to compute for minimum (True) or maximum (False)
22      
23        Returns:
24            The total sum contribution
25        """
26        n = len(nums)
27        # Arrays to store the previous and next element indices
28        # where the monotonic property breaks
29        previous_boundary = [-1] * n
30        next_boundary = [n] * n
31        stack = []
32      
33        if is_min:
34            # Find previous smaller element for each position
35            for i in range(n):
36                while stack and nums[stack[-1]] >= nums[i]:
37                    stack.pop()
38                previous_boundary[i] = stack[-1] if stack else -1
39                stack.append(i)
40          
41            # Reset stack for next computation
42            stack = []
43          
44            # Find next smaller or equal element for each position
45            for i in range(n - 1, -1, -1):
46                while stack and nums[stack[-1]] > nums[i]:
47                    stack.pop()
48                next_boundary[i] = stack[-1] if stack else n
49                stack.append(i)
50        else:
51            # Find previous greater element for each position
52            for i in range(n):
53                while stack and nums[stack[-1]] <= nums[i]:
54                    stack.pop()
55                previous_boundary[i] = stack[-1] if stack else -1
56                stack.append(i)
57          
58            # Reset stack for next computation
59            stack = []
60          
61            # Find next greater or equal element for each position
62            for i in range(n - 1, -1, -1):
63                while stack and nums[stack[-1]] < nums[i]:
64                    stack.pop()
65                next_boundary[i] = stack[-1] if stack else n
66                stack.append(i)
67      
68        total_sum = 0
69      
70        # Calculate contribution of each element as min/max in subarrays
71        for i in range(n):
72            left_bound = previous_boundary[i]
73            right_bound = next_boundary[i]
74          
75            # Define range boundaries where current element is min/max
76            range_start = left_bound + 1
77            current_position = i
78            range_end = right_bound - 1
79          
80            # Calculate valid starting positions for subarrays of length k
81            # where current element is included and is the min/max
82            valid_start_position = max(range_start, i - k + 1)
83            last_possible_start = range_end - k + 1
84            upper_bound_start = min(current_position, last_possible_start)
85          
86            # Calculate sum for type 1 subarrays
87            sum_type1 = 0
88            if upper_bound_start >= valid_start_position:
89                number_of_terms = upper_bound_start - valid_start_position + 1
90                first_term = valid_start_position
91                last_term = upper_bound_start
92                # Sum of arithmetic sequence for starting positions
93                sum_of_indices = (last_term * (last_term + 1)) // 2 - ((first_term - 1) * first_term) // 2
94                constant_component = (k - i) * number_of_terms
95                sum_type1 = sum_of_indices + constant_component
96          
97            # Calculate range for type 2 subarrays
98            start_type2 = upper_bound_start + 1
99            end_type2 = current_position
100            start_type2 = max(start_type2, range_start)
101            end_type2 = min(end_type2, current_position)
102          
103            # Calculate sum for type 2 subarrays
104            sum_type2 = 0
105            if start_type2 <= end_type2:
106                count_type2 = end_type2 - start_type2 + 1
107                multiplier = range_end - i + 1
108                sum_type2 = multiplier * count_type2
109          
110            # Add contribution of current element multiplied by number of subarrays
111            total_sum += nums[i] * (sum_type1 + sum_type2)
112      
113        return total_sum
114  
115    # Calculate sum of minimums and sum of maximums
116    minimum_sum = compute_sum(nums, k, True)
117    maximum_sum = compute_sum(nums, k, False)
118  
119    return minimum_sum + maximum_sum
120
1/**
2 * Calculates the sum of minimum and maximum values across all subarrays of length k
3 * @param nums - The input array of numbers
4 * @param k - The length of subarrays to consider
5 * @return The sum of all minimum values plus the sum of all maximum values
6 */
7public class Solution {
8    public long minMaxSubarraySum(int[] nums, int k) {
9        // Calculate sum of minimums and sum of maximums
10        long minimumSum = computeSum(nums, k, true);
11        long maximumSum = computeSum(nums, k, false);
12      
13        return minimumSum + maximumSum;
14    }
15  
16    /**
17     * Computes the sum contribution of either minimum or maximum elements
18     * across all subarrays of length k
19     * @param nums - The input array
20     * @param k - The subarray length
21     * @param isMin - Whether to compute for minimum (true) or maximum (false)
22     * @return The total sum contribution
23     */
24    private long computeSum(int[] nums, int k, boolean isMin) {
25        int n = nums.length;
26        // Arrays to store the previous and next element indices
27        // where the monotonic property breaks
28        int[] previousBoundary = new int[n];
29        int[] nextBoundary = new int[n];
30        Arrays.fill(previousBoundary, -1);
31        Arrays.fill(nextBoundary, n);
32      
33        Stack<Integer> stack = new Stack<>();
34      
35        if (isMin) {
36            // Find previous smaller element for each position
37            for (int i = 0; i < n; i++) {
38                while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
39                    stack.pop();
40                }
41                previousBoundary[i] = stack.isEmpty() ? -1 : stack.peek();
42                stack.push(i);
43            }
44          
45            // Reset stack for next computation
46            stack.clear();
47          
48            // Find next smaller or equal element for each position
49            for (int i = n - 1; i >= 0; i--) {
50                while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
51                    stack.pop();
52                }
53                nextBoundary[i] = stack.isEmpty() ? n : stack.peek();
54                stack.push(i);
55            }
56        } else {
57            // Find previous greater element for each position
58            for (int i = 0; i < n; i++) {
59                while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
60                    stack.pop();
61                }
62                previousBoundary[i] = stack.isEmpty() ? -1 : stack.peek();
63                stack.push(i);
64            }
65          
66            // Reset stack for next computation
67            stack.clear();
68          
69            // Find next greater or equal element for each position
70            for (int i = n - 1; i >= 0; i--) {
71                while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
72                    stack.pop();
73                }
74                nextBoundary[i] = stack.isEmpty() ? n : stack.peek();
75                stack.push(i);
76            }
77        }
78      
79        long totalSum = 0;
80      
81        // Calculate contribution of each element as min/max in subarrays
82        for (int i = 0; i < n; i++) {
83            int leftBound = previousBoundary[i];
84            int rightBound = nextBoundary[i];
85          
86            // Define range boundaries where current element is min/max
87            int rangeStart = leftBound + 1;
88            int currentPosition = i;
89            int rangeEnd = rightBound - 1;
90          
91            // Calculate valid starting positions for subarrays of length k
92            // where current element is included and is the min/max
93            int validStartPosition = Math.max(rangeStart, i - k + 1);
94            int lastPossibleStart = rangeEnd - k + 1;
95            int upperBoundStart = Math.min(currentPosition, lastPossibleStart);
96          
97            // Calculate sum for type 1 subarrays
98            long sumType1 = 0;
99            if (upperBoundStart >= validStartPosition) {
100                long numberOfTerms = upperBoundStart - validStartPosition + 1;
101                long firstTerm = validStartPosition;
102                long lastTerm = upperBoundStart;
103                // Sum of arithmetic sequence for starting positions
104                long sumOfIndices = (lastTerm * (lastTerm + 1)) / 2 - 
105                                   ((firstTerm - 1) * firstTerm) / 2;
106                long constantComponent = (k - i) * numberOfTerms;
107                sumType1 = sumOfIndices + constantComponent;
108            }
109          
110            // Calculate range for type 2 subarrays
111            int startType2 = upperBoundStart + 1;
112            int endType2 = currentPosition;
113            startType2 = Math.max(startType2, rangeStart);
114            endType2 = Math.min(endType2, currentPosition);
115          
116            // Calculate sum for type 2 subarrays
117            long sumType2 = 0;
118            if (startType2 <= endType2) {
119                long countType2 = endType2 - startType2 + 1;
120                long multiplier = rangeEnd - i + 1;
121                sumType2 = multiplier * countType2;
122            }
123          
124            // Add contribution of current element multiplied by number of subarrays
125            totalSum += (long)nums[i] * (sumType1 + sumType2);
126        }
127      
128        return totalSum;
129    }
130}
131
1#include <vector>
2#include <algorithm>
3#include <stack>
4
5class Solution {
6public:
7    /**
8     * Calculates the sum of minimum and maximum values across all subarrays of length k
9     * @param nums - The input array of numbers
10     * @param k - The length of subarrays to consider
11     * @return The sum of all minimum values plus the sum of all maximum values
12     */
13    long long minMaxSubarraySum(std::vector<int>& nums, int k) {
14        // Calculate sum of minimums and sum of maximums
15        long long minimumSum = computeSum(nums, k, true);
16        long long maximumSum = computeSum(nums, k, false);
17      
18        return minimumSum + maximumSum;
19    }
20  
21private:
22    /**
23     * Computes the sum contribution of either minimum or maximum elements
24     * across all subarrays of length k
25     * @param nums - The input array
26     * @param k - The subarray length
27     * @param isMin - Whether to compute for minimum (true) or maximum (false)
28     * @return The total sum contribution
29     */
30    long long computeSum(const std::vector<int>& nums, int k, bool isMin) {
31        int n = nums.size();
32        // Arrays to store the previous and next element indices
33        // where the monotonic property breaks
34        std::vector<int> previousBoundary(n, -1);
35        std::vector<int> nextBoundary(n, n);
36        std::stack<int> stack;
37      
38        if (isMin) {
39            // Find previous smaller element for each position
40            for (int i = 0; i < n; i++) {
41                while (!stack.empty() && nums[stack.top()] >= nums[i]) {
42                    stack.pop();
43                }
44                previousBoundary[i] = stack.empty() ? -1 : stack.top();
45                stack.push(i);
46            }
47          
48            // Reset stack for next computation
49            while (!stack.empty()) {
50                stack.pop();
51            }
52          
53            // Find next smaller or equal element for each position
54            for (int i = n - 1; i >= 0; i--) {
55                while (!stack.empty() && nums[stack.top()] > nums[i]) {
56                    stack.pop();
57                }
58                nextBoundary[i] = stack.empty() ? n : stack.top();
59                stack.push(i);
60            }
61        } else {
62            // Find previous greater element for each position
63            for (int i = 0; i < n; i++) {
64                while (!stack.empty() && nums[stack.top()] <= nums[i]) {
65                    stack.pop();
66                }
67                previousBoundary[i] = stack.empty() ? -1 : stack.top();
68                stack.push(i);
69            }
70          
71            // Reset stack for next computation
72            while (!stack.empty()) {
73                stack.pop();
74            }
75          
76            // Find next greater or equal element for each position
77            for (int i = n - 1; i >= 0; i--) {
78                while (!stack.empty() && nums[stack.top()] < nums[i]) {
79                    stack.pop();
80                }
81                nextBoundary[i] = stack.empty() ? n : stack.top();
82                stack.push(i);
83            }
84        }
85      
86        long long totalSum = 0;
87      
88        // Calculate contribution of each element as min/max in subarrays
89        for (int i = 0; i < n; i++) {
90            int leftBound = previousBoundary[i];
91            int rightBound = nextBoundary[i];
92          
93            // Define range boundaries where current element is min/max
94            int rangeStart = leftBound + 1;
95            int currentPosition = i;
96            int rangeEnd = rightBound - 1;
97          
98            // Calculate valid starting positions for subarrays of length k
99            // where current element is included and is the min/max
100            int validStartPosition = std::max(rangeStart, i - k + 1);
101            int lastPossibleStart = rangeEnd - k + 1;
102            int upperBoundStart = std::min(currentPosition, lastPossibleStart);
103          
104            // Calculate sum for type 1 subarrays
105            long long sumType1 = 0;
106            if (upperBoundStart >= validStartPosition) {
107                long long numberOfTerms = upperBoundStart - validStartPosition + 1;
108                long long firstTerm = validStartPosition;
109                long long lastTerm = upperBoundStart;
110                // Sum of arithmetic sequence for starting positions
111                long long sumOfIndices = (lastTerm * (lastTerm + 1)) / 2 - 
112                                        ((firstTerm - 1) * firstTerm) / 2;
113                long long constantComponent = (k - i) * numberOfTerms;
114                sumType1 = sumOfIndices + constantComponent;
115            }
116          
117            // Calculate range for type 2 subarrays
118            int startType2 = upperBoundStart + 1;
119            int endType2 = currentPosition;
120            startType2 = std::max(startType2, rangeStart);
121            endType2 = std::min(endType2, currentPosition);
122          
123            // Calculate sum for type 2 subarrays
124            long long sumType2 = 0;
125            if (startType2 <= endType2) {
126                long long countType2 = endType2 - startType2 + 1;
127                long long multiplier = rangeEnd - i + 1;
128                sumType2 = multiplier * countType2;
129            }
130          
131            // Add contribution of current element multiplied by number of subarrays
132            totalSum += static_cast<long long>(nums[i]) * (sumType1 + sumType2);
133        }
134      
135        return totalSum;
136    }
137};
138
1/**
2 * Calculates the sum of minimum and maximum values across all subarrays of length k
3 * @param nums - The input array of numbers
4 * @param k - The length of subarrays to consider
5 * @returns The sum of all minimum values plus the sum of all maximum values
6 */
7function minMaxSubarraySum(nums: number[], k: number): number {
8    /**
9     * Computes the sum contribution of either minimum or maximum elements
10     * across all subarrays of length k
11     * @param nums - The input array
12     * @param k - The subarray length
13     * @param isMin - Whether to compute for minimum (true) or maximum (false)
14     * @returns The total sum contribution
15     */
16    const computeSum = (nums: number[], k: number, isMin: boolean): number => {
17        const n: number = nums.length;
18        // Arrays to store the previous and next element indices
19        // where the monotonic property breaks
20        const previousBoundary: number[] = Array(n).fill(-1);
21        const nextBoundary: number[] = Array(n).fill(n);
22        let stack: number[] = [];
23
24        if (isMin) {
25            // Find previous smaller element for each position
26            for (let i = 0; i < n; i++) {
27                while (stack.length > 0 && nums[stack[stack.length - 1]] >= nums[i]) {
28                    stack.pop();
29                }
30                previousBoundary[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
31                stack.push(i);
32            }
33          
34            // Reset stack for next computation
35            stack = [];
36          
37            // Find next smaller or equal element for each position
38            for (let i = n - 1; i >= 0; i--) {
39                while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
40                    stack.pop();
41                }
42                nextBoundary[i] = stack.length > 0 ? stack[stack.length - 1] : n;
43                stack.push(i);
44            }
45        } else {
46            // Find previous greater element for each position
47            for (let i = 0; i < n; i++) {
48                while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[i]) {
49                    stack.pop();
50                }
51                previousBoundary[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
52                stack.push(i);
53            }
54          
55            // Reset stack for next computation
56            stack = [];
57          
58            // Find next greater or equal element for each position
59            for (let i = n - 1; i >= 0; i--) {
60                while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
61                    stack.pop();
62                }
63                nextBoundary[i] = stack.length > 0 ? stack[stack.length - 1] : n;
64                stack.push(i);
65            }
66        }
67
68        let totalSum: number = 0;
69      
70        // Calculate contribution of each element as min/max in subarrays
71        for (let i = 0; i < n; i++) {
72            const leftBound: number = previousBoundary[i];
73            const rightBound: number = nextBoundary[i];
74          
75            // Define range boundaries where current element is min/max
76            const rangeStart: number = leftBound + 1;
77            const currentPosition: number = i;
78            const rangeEnd: number = rightBound - 1;
79
80            // Calculate valid starting positions for subarrays of length k
81            // where current element is included and is the min/max
82            const validStartPosition: number = Math.max(rangeStart, i - k + 1);
83            const lastPossibleStart: number = rangeEnd - k + 1;
84            const upperBoundStart: number = Math.min(currentPosition, lastPossibleStart);
85
86            // Calculate sum for type 1 subarrays
87            let sumType1: number = 0;
88            if (upperBoundStart >= validStartPosition) {
89                const numberOfTerms: number = upperBoundStart - validStartPosition + 1;
90                const firstTerm: number = validStartPosition;
91                const lastTerm: number = upperBoundStart;
92                // Sum of arithmetic sequence for starting positions
93                const sumOfIndices: number = (lastTerm * (lastTerm + 1)) / 2 - 
94                                            ((firstTerm - 1) * firstTerm) / 2;
95                const constantComponent: number = (k - i) * numberOfTerms;
96                sumType1 = sumOfIndices + constantComponent;
97            }
98
99            // Calculate range for type 2 subarrays
100            let startType2: number = upperBoundStart + 1;
101            let endType2: number = currentPosition;
102            startType2 = Math.max(startType2, rangeStart);
103            endType2 = Math.min(endType2, currentPosition);
104
105            // Calculate sum for type 2 subarrays
106            let sumType2: number = 0;
107            if (startType2 <= endType2) {
108                const countType2: number = endType2 - startType2 + 1;
109                const multiplier: number = rangeEnd - i + 1;
110                sumType2 = multiplier * countType2;
111            }
112
113            // Add contribution of current element multiplied by number of subarrays
114            totalSum += nums[i] * (sumType1 + sumType2);
115        }
116
117        return totalSum;
118    };
119
120    // Calculate sum of minimums and sum of maximums
121    const minimumSum: number = computeSum(nums, k, true);
122    const maximumSum: number = computeSum(nums, k, false);
123  
124    return minimumSum + maximumSum;
125}
126

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm consists of the following operations:

  • The computeSum function is called twice (once for minimum, once for maximum)
  • Inside computeSum:
    • Building the prev array using a monotonic stack: O(n) - each element is pushed and popped at most once
    • Building the next array using a monotonic stack: O(n) - each element is pushed and popped at most once
    • Computing the contribution of each element: O(n) - iterating through each element once with O(1) operations per element (arithmetic calculations)
  • The final addition of minSum and maxSum: O(1)

Since all operations are linear and performed sequentially, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n) where n is the length of the input array nums.

The algorithm uses the following additional space:

  • prev array: O(n) space
  • next array: O(n) space
  • stk (stack): O(n) space in the worst case when all elements are monotonic
  • A few scalar variables (totalSum, minSum, maxSum, loop variables): O(1) space

The maximum space used at any point is O(n) for the arrays and stack, resulting in an overall space complexity of O(n).

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

Common Pitfalls

1. Incorrect Boundary Calculation for Valid Subarrays

The Pitfall: One of the most common mistakes is incorrectly calculating which subarrays are valid when an element serves as the minimum/maximum. The code must ensure that:

  • The subarray length doesn't exceed k
  • The subarray stays within the dominance range of the element
  • The arithmetic for counting valid positions is correct

For example, when calculating upper_bound_start = min(current_position, last_possible_start), forgetting either constraint leads to counting invalid subarrays:

# WRONG: Only considering one constraint
upper_bound_start = last_possible_start  # Ignores that we can't start after position i
# OR
upper_bound_start = current_position  # Ignores the k-length constraint

Solution: Always apply both constraints:

last_possible_start = range_end - k + 1  # Ensures subarray fits before range_end
upper_bound_start = min(current_position, last_possible_start)  # Apply both constraints

2. Off-by-One Errors in Range Calculations

The Pitfall: The dominance range boundaries are particularly prone to off-by-one errors. The code uses:

  • range_start = left_bound + 1 (inclusive)
  • range_end = right_bound - 1 (inclusive)

A common mistake is treating these as exclusive boundaries or miscalculating the number of elements:

# WRONG: Treating range_end as exclusive
number_of_subarrays = range_end - range_start  # Missing the +1
# CORRECT:
number_of_subarrays = range_end - range_start + 1

Solution: Be consistent with inclusive/exclusive boundaries and always verify the count calculation:

# When both boundaries are inclusive:
count = end - start + 1
# When start is inclusive, end is exclusive:
count = end - start

3. Monotonic Stack Comparison Logic

The Pitfall: The comparison operators in the monotonic stack must be carefully chosen to handle duplicates correctly:

  • For minimum: Use >= when popping (not just >)
  • For maximum: Use <= when popping (not just <)
# WRONG for minimum calculation:
while stack and nums[stack[-1]] > nums[i]:  # Misses equal elements
    stack.pop()

# CORRECT for minimum calculation:
while stack and nums[stack[-1]] >= nums[i]:  # Handles duplicates properly
    stack.pop()

This ensures that when there are duplicate values, we correctly identify the range where each element is the minimum/maximum.

Solution: Use strict inequality for one direction and non-strict for the other to handle duplicates:

# For minimum:
# Previous: strictly less (use >=)
# Next: less or equal (use >)

# For maximum:
# Previous: strictly greater (use <=)  
# Next: greater or equal (use <)

4. Integer Overflow in Sum Calculations

The Pitfall: The arithmetic sequence sum calculation can cause overflow for large values:

sum_of_indices = (last_term * (last_term + 1)) // 2

For large arrays, last_term * (last_term + 1) might overflow before the division.

Solution: In Python, this isn't typically an issue due to arbitrary precision integers, but in other languages, consider:

  • Using appropriate data types (long/int64)
  • Rearranging calculations to minimize intermediate values
  • Breaking down the calculation into smaller parts

5. Incorrect Handling of Edge Cases

The Pitfall: Not properly handling edge cases such as:

  • k = 1: All subarrays are single elements
  • k >= n: All possible subarrays are valid
  • Single element arrays
  • Arrays where all elements are the same

Solution: Test these edge cases explicitly:

# Add validation at the start
if not nums:
    return 0
if k <= 0:
    return 0
n = len(nums)
k = min(k, n)  # Cap k at array length

6. Misunderstanding the Problem Statement

The Pitfall: Confusing "subarrays of length at most k" with "subarrays of exactly length k". The problem asks for ALL subarrays with length from 1 to k, not just those of length k.

Solution: The code correctly handles this by considering all valid positions within the k-length constraint, but it's important to understand that we're summing contributions from subarrays of various lengths (1, 2, ..., up to k).

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

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