Problem Description

You are given an array of integers arr. Your task is to find the sum of minimum values across all possible contiguous subarrays of arr.

For example, if arr = [3, 1, 2, 4], the contiguous subarrays are:

• [3] with minimum value 3
• [3, 1] with minimum value 1
• [3, 1, 2] with minimum value 1
• [3, 1, 2, 4] with minimum value 1
• [1] with minimum value 1
• [1, 2] with minimum value 1
• [1, 2, 4] with minimum value 1
• [2] with minimum value 2
• [2, 4] with minimum value 2
• [4] with minimum value 4

The sum of all these minimum values is 3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17.

Since the answer can be very large, return the result modulo 10^9 + 7.

The solution uses a monotonic stack approach to efficiently calculate how many subarrays have each element as their minimum value. For each element arr[i], it finds:

• left[i]: the index of the nearest element to the left that is smaller than arr[i] (or -1 if none exists)
• right[i]: the index of the nearest element to the right that is smaller than or equal to arr[i] (or n if none exists)

The number of subarrays where arr[i] is the minimum is (i - left[i]) × (right[i] - i). This represents all possible subarrays that can be formed by choosing a starting point between left[i] + 1 and i, and an ending point between i and right[i] - 1.

The asymmetry in the comparison (using >= for left boundary but > for right boundary) prevents counting duplicate subarrays when there are equal elements in the array.

Intuition

Instead of finding the minimum for every possible subarray (which would be inefficient), we can flip the problem around: for each element, count how many subarrays have that element as their minimum value, then multiply by the element's value.

Think about it this way - if an element arr[i] is the minimum in 10 different subarrays, it contributes arr[i] × 10 to our final sum. So the key question becomes: how many subarrays have arr[i] as their minimum?

For arr[i] to be the minimum of a subarray, that subarray cannot extend beyond any smaller elements on either side. This means:

• The subarray cannot include any element to the left that is smaller than arr[i]
• The subarray cannot include any element to the right that is smaller than arr[i]

So we need to find the "boundaries" for each element - how far left and right can we extend while arr[i] remains the minimum?

If we find:

• The nearest smaller element to the left at position left[i]
• The nearest smaller element to the right at position right[i]

Then any subarray containing arr[i] as its minimum must:

• Start somewhere between left[i] + 1 and i (we have i - left[i] choices)
• End somewhere between i and right[i] - 1 (we have right[i] - i choices)

Total subarrays with arr[i] as minimum = (i - left[i]) × (right[i] - i)

A monotonic stack is perfect for finding "nearest smaller element" problems. We maintain a stack of indices where the corresponding values are in increasing order. When we encounter a new element:

• Pop elements from the stack that are greater than or equal to the current element
• The top of the stack (if any remains) gives us the nearest smaller element
• Push the current element's index onto the stack

We do this twice - once from left to right to find left[i], and once from right to left to find right[i]. The slight asymmetry (using >= for left but > for right) handles duplicate values correctly, ensuring each subarray is counted exactly once.

Learn more about Stack, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The implementation uses a monotonic stack to find the boundaries for each element efficiently in O(n) time.

Step 1: Initialize Arrays

• Create left array initialized with -1 (representing no smaller element to the left)
• Create right array initialized with n (representing no smaller element to the right)
• These arrays will store the boundaries for each element

Step 2: Find Left Boundaries We traverse the array from left to right with a monotonic stack:

stk = []
for i, v in enumerate(arr):
    while stk and arr[stk[-1]] >= v:
        stk.pop()
    if stk:
        left[i] = stk[-1]
    stk.append(i)

• The stack maintains indices of elements in increasing order of their values
• When we see element v at index i:
  • Pop all elements from stack that are >= v (they can't be the left boundary)
  • The remaining top element (if any) is the nearest smaller element to the left
  • Push current index i to maintain the monotonic property

Step 3: Find Right Boundaries We traverse the array from right to left with a fresh monotonic stack:

stk = []
for i in range(n - 1, -1, -1):
    while stk and arr[stk[-1]] > arr[i]:
        stk.pop()
    if stk:
        right[i] = stk[-1]
    stk.append(i)

• Similar process but moving right to left
• Note the condition is > (not >=) to handle duplicates correctly
• This ensures that when multiple elements have the same value, only one of them "claims" each subarray

Step 4: Calculate the Sum

sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod

For each element at index i with value v:

• (i - left[i]) = number of possible starting positions for subarrays
• (right[i] - i) = number of possible ending positions for subarrays
• Total contribution = (i - left[i]) × (right[i] - i) × v

Why the Asymmetry in Comparisons? Using >= for left boundaries and > for right boundaries prevents double-counting when duplicate values exist. Consider array [2, 3, 2]:

• For the first 2 at index 0: left boundary is -1, right boundary is 2
• For the second 2 at index 2: left boundary is -1, right boundary is 3
• This ensures subarray [2, 3, 2] is counted only once (for the first 2)

Time Complexity: O(n) - each element is pushed and popped from the stack at most once Space Complexity: O(n) - for the left, right arrays and stack

Example Walkthrough

Let's walk through the solution with a small example: arr = [3, 1, 2, 4]

Step 1: Find Left Boundaries (nearest smaller element to the left)

We traverse left to right with a monotonic stack:

• i=0, v=3: Stack is empty → left[0] = -1, push 0. Stack: [0]
• i=1, v=1: Pop 0 (since arr[0]=3 >= 1) → Stack empty → left[1] = -1, push 1. Stack: [1]
• i=2, v=2: arr[1]=1 < 2, keep it → left[2] = 1, push 2. Stack: [1, 2]
• i=3, v=4: arr[2]=2 < 4, keep it → left[3] = 2, push 3. Stack: [1, 2, 3]

Result: left = [-1, -1, 1, 2]

Step 2: Find Right Boundaries (nearest smaller or equal element to the right)

We traverse right to left with a fresh stack:

• i=3, v=4: Stack is empty → right[3] = 4, push 3. Stack: [3]
• i=2, v=2: Pop 3 (since arr[3]=4 > 2) → Stack empty → right[2] = 4, push 2. Stack: [2]
• i=1, v=1: Pop 2 (since arr[2]=2 > 1) → Stack empty → right[1] = 4, push 1. Stack: [1]
• i=0, v=3: arr[1]=1 not > 3, keep it → right[0] = 1, push 0. Stack: [1, 0]

Result: right = [1, 4, 4, 4]

Step 3: Calculate Contributions

For each element, calculate how many subarrays have it as minimum:

• arr[0] = 3:

  • Can start from indices: 0 to 0 (since left[0]=-1) → 1 choice
  • Can end at indices: 0 to 0 (since right[0]=1) → 1 choice
  • Subarrays: [3] → Count = 1 × 1 = 1
  • Contribution: 3 × 1 = 3

• arr[1] = 1:

  • Can start from indices: 0 to 1 (since left[1]=-1) → 2 choices
  • Can end at indices: 1 to 3 (since right[1]=4) → 3 choices
  • Subarrays: [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4] → Count = 2 × 3 = 6
  • Contribution: 1 × 6 = 6

• arr[2] = 2:

  • Can start from indices: 2 to 2 (since left[2]=1) → 1 choice
  • Can end at indices: 2 to 3 (since right[2]=4) → 2 choices
  • Subarrays: [2], [2,4] → Count = 1 × 2 = 2
  • Contribution: 2 × 2 = 4

• arr[3] = 4:

  • Can start from indices: 3 to 3 (since left[3]=2) → 1 choice
  • Can end at indices: 3 to 3 (since right[3]=4) → 1 choice
  • Subarrays: [4] → Count = 1 × 1 = 1
  • Contribution: 4 × 1 = 4

Total Sum: 3 + 6 + 4 + 4 = 17

This matches our expected result! The monotonic stack approach efficiently found the boundaries for each element, allowing us to calculate each element's contribution to the final sum in O(n) time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main parts:

• First loop: Iterates through the array once to fill the left array using a monotonic stack. Each element is pushed and popped from the stack at most once, resulting in O(n) operations.
• Second loop: Iterates through the array in reverse to fill the right array using a monotonic stack. Similarly, each element is pushed and popped at most once, resulting in O(n) operations.
• Final sum calculation: Iterates through the array once to compute the sum, performing O(1) operations for each element, totaling O(n).

Overall time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n)

The algorithm uses the following additional space:

• left array: stores n elements, requiring O(n) space
• right array: stores n elements, requiring O(n) space
• stk (stack): can contain at most n elements in the worst case, requiring O(n) space

Overall space complexity: O(n) + O(n) + O(n) = O(n)

where n is the length of the array arr.

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

Common Pitfalls

1. Incorrect Handling of Duplicates

One of the most common mistakes is using symmetric comparisons for both left and right boundaries. If you use >= for both directions or > for both directions, you'll either double-count or miss subarrays when duplicate values exist.

Incorrect Implementation:

# WRONG: Using >= for both boundaries
for i, v in enumerate(arr):
    while stk and arr[stk[-1]] >= v:  # Left boundary
        stk.pop()
  
# Later...
for i in range(n - 1, -1, -1):
    while stk and arr[stk[-1]] >= arr[i]:  # Right boundary - WRONG!
        stk.pop()

Problem Example: For array [2, 2, 2], using >= for both would cause each element to claim no subarrays (each would have boundaries that exclude themselves), resulting in 0 instead of the correct answer.

Solution: Use >= for left boundary and > for right boundary (or vice versa, but be consistent):

# Correct: >= for left, > for right
while stk and arr[stk[-1]] >= v:      # Left boundary
while stk and arr[stk[-1]] > arr[i]:  # Right boundary

2. Integer Overflow

The sum can become very large before applying modulo, potentially causing overflow in languages with fixed integer sizes.

Incorrect Implementation:

# WRONG: Applying modulo only at the end
total = 0
for i, v in enumerate(arr):
    total += (i - left[i]) * (right[i] - i) * v
return total % MOD  # Overflow may have already occurred

Solution: Apply modulo during accumulation or use Python's arbitrary precision integers:

# Better: Apply modulo during accumulation if needed
total = 0
for i, v in enumerate(arr):
    contribution = (i - left[i]) * (right[i] - i) * v
    total = (total + contribution) % MOD
return total

3. Stack Reuse Without Clearing

Forgetting to clear or reinitialize the stack between finding left and right boundaries.

Incorrect Implementation:

stk = []
# Find left boundaries
for i, v in enumerate(arr):
    # ... process left boundaries
  
# WRONG: Forgot to clear stack!
# stk still contains elements from left boundary calculation
for i in range(n - 1, -1, -1):
    # ... process right boundaries with dirty stack

Solution: Always reinitialize the stack:

stk = []
# Find left boundaries
for i, v in enumerate(arr):
    # ... process left boundaries

stk = []  # Clear the stack!
# Find right boundaries
for i in range(n - 1, -1, -1):
    # ... process right boundaries

4. Incorrect Boundary Initialization

Using wrong default values for boundaries can lead to incorrect subarray counts.

Incorrect Implementation:

# WRONG: Initializing with 0 instead of -1 for left
left = [0] * n  # Should be -1
right = [n-1] * n  # Should be n

Problem: This would incorrectly calculate the number of subarrays. For example, if arr[0] has no smaller element to its left, using left[0] = 0 would give (0 - 0) = 0 subarrays instead of (0 - (-1)) = 1.

Solution: Use -1 for left boundaries and n for right boundaries:

left = [-1] * n   # Correct: -1 indicates no smaller element to the left
right = [n] * n   # Correct: n indicates no smaller element to the right