Problem Statement

Given an array of integers arr, return the sum of the minimum values from all possible contiguous subarrays within arr. Since the result can be very large, return the final sum modulo (10⁹ + 7).

Examples

Example 1:

• Input: arr = [3, 1, 2, 4, 5]
• Expected Output: 30
• Explanation:
  • The subarrays are: [3], [1], [2], [4], [5], [3,1], [1,2], [2,4], [4,5], [3,1,2], [1,2,4], [2,4,5], [3,1,2,4], [1, 2, 4, 5], [3, 1, 2, 4, 5].
  • The minimum values of these subarrays are: 3, 1, 2, 4, 5, 1, 1, 2, 4, 1, 1, 2, 1, 1, 1.
  • Summing these minimums: 3 + 1 + 2 + 4 + 5 + 1 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 30.

Example 2:

• Input: arr = [2, 6, 5, 4]
• Expected Output: 36
• Explanation:
  • The subarrays are: [2], [6], [5], [4], [2,6], [6,5], [5,4], [2,6,5], [6,5,4], [2,6,5,4].
  • The minimum values of these subarrays are: 2, 6, 5, 4, 2, 5, 4, 2, 4, 2.
  • Summing these minimums: 2 + 6 + 5 + 4 + 2 + 5 + 4 + 2 + 4 + 2 = 36.

Example 3:

• Input: arr = [7, 3, 8]
• Expected Output: 35
• Explanation:
  • The subarrays are: [7], [3], [8], [7,3], [3,8], [7,3,8].
  • The minimum values of these subarrays are: 7, 3, 8, 3, 3, 3.
  • Summing these minimums: 7 + 3 + 8 + 3 + 3 + 3 = 27.

Constraints:

• 1 <= arr.length <= 3 * 10⁴
• 1 <= arr[i] <= 3 * 10⁴

Solution

To find the sum of the minimum values of all subarrays in an array, we use a Monotonic Stack. Instead of checking every possible subarray one by one (which would be slow), we use a stack to efficiently determine how many subarrays have a particular element as their minimum.

The stack helps us keep track of indices of array elements in increasing order. This means that as we move through the array, each element in the stack is smaller than or equal to the next. Whenever we encounter an element that is smaller than the top of the stack, it means that the element at the top of the stack can no longer be the minimum for future subarrays. At this point, we remove (pop) the element from the stack and calculate how many subarrays it was the minimum for.

For each popped element, we determine two key things:

1. How many subarrays end at this element?
   • This is found by checking the difference between its position and the previous element in the stack.
2. How many subarrays start at this element?
   • This is found by checking the difference between its position and the current index.

By multiplying these two values, we find the total number of subarrays where this element is the minimum, and we add its contribution to the result.

This approach is efficient because instead of checking all possible subarrays, we process each element only when we push it onto the stack and pop it off. This results in an O(n) time complexity, making the solution much faster than a brute-force approach.

Step-by-Step Algorithm

Step-by-Step Algorithm (Simplified & Improved Explanation)

1. Initialize Variables:

   • Define MOD = 10^9 + 7 to keep the result within the problem’s constraints.
   • Create a variable result and set it to 0 to accumulate the sum of subarray minimums.
   • Initialize a Monotonic Stack using Stack<Integer> to store indices. The stack will help track the position of elements while maintaining an increasing order of values.

2. Iterate Through the Array:

   • Loop through the array using an index currentIndex from 0 to n (where n is the length of the array). The extra iteration at n is to handle a sentinel value (0) that ensures all remaining elements in the stack are processed.
   • For each iteration:
     • Determine the Current Element:
       • If currentIndex < n, set currentElement = arr[currentIndex].
       • Otherwise, set currentElement = 0 (to process any remaining elements in the stack).

3. Process the Stack:

   • If the stack is not empty and the top element in the stack is greater than the current element, this means that the top element cannot be the minimum in future subarrays.
   • While this condition holds, pop elements from the stack and calculate their contribution:

     • Find Subarrays Where the Popped Element is the Minimum:

       • The popped index (minElementIndex) represents the element that is being processed.
       • The previous element in the stack (if any) gives the left boundary (previousIndex). If the stack is empty, previousIndex = -1.
       • The count of subarrays where arr[minElementIndex] is the minimum is calculated as:
         • Subarrays ending at minElementIndex → (minElementIndex - previousIndex)
         • Subarrays starting at minElementIndex → (currentIndex - minElementIndex)
         • The total number of subarrays where arr[minElementIndex] is the minimum is the product of these two values.

     • Update the Result:

       • Multiply arr[minElementIndex] by countSubarrays to get the total contribution of this element.
       • Apply modulo (10^9 + 7) to ensure that the result does not exceed constraints:

         result = (result + (long) arr[minElementIndex] * countSubarrays % MOD) % MOD;

4. Push the Current Index onto the Stack:

   • After processing, add currentIndex to the stack to track future elements.

5. Return the Final Result:

   • After iterating through all elements, return result % MOD as the final answer.

Algorithm Walkthrough

Let's walk through the algorithm with the array arr = [3, 1, 2, 4, 5]:

1. Initialization

• MOD = 1_000_000_007
• result = 0
• stack = []
• n = 5

2. First Iteration (currentIndex = 0):

• currentElement = 3
• The stack is empty, so push 0.
• stack = [0]
• result = 0

3. Second Iteration (currentIndex = 1):

• currentElement = 1
• arr[0] > 1 (3 > 1), so pop 0 from the stack:
  • minElementIndex = 0
  • previousIndex = -1
  • countSubarrays = (0 - (-1)) * (1 - 0) = 1 * 1 = 1
  • result = (0 + 3 * 1 % MOD) % MOD = 3
• Push 1 to the stack.
• stack = [1]
• result = 3

4. Third Iteration (currentIndex = 2):

• currentElement = 2
• arr[1] < 2 (1 < 2), so no popping occurs.
• Push 2 to the stack.
• stack = [1, 2]
• result = 3

5. Fourth Iteration (currentIndex = 3):

• currentElement = 4
• arr[2] < 4 (2 < 4), so no popping occurs.
• Push 3 to the stack.
• stack = [1, 2, 3]
• result = 3

6. Fifth Iteration (currentIndex = 4):

• currentElement = 5
• arr[3] < 5 (4 < 5), so no popping occurs.
• Push 4 to the stack.
• stack = [1, 2, 3, 4]
• result = 3

7. Final Iteration (currentIndex = 5, Sentinel):

• currentElement = 0
• Pop elements from the stack because all are greater than 0:
  • Pop 4:
    • minElementIndex = 4
    • previousIndex = 3
    • countSubarrays = (4 - 3) * (5 - 4) = 1 * 1 = 1
    • result = (3 + 5 * 1 % MOD) % MOD = 8
  • Pop 3:
    • minElementIndex = 3
    • previousIndex = 2
    • countSubarrays = (3 - 2) * (5 - 3) = 1 * 2 = 2
    • result = (8 + 4 * 2 % MOD) % MOD = 16
  • Pop 2:
    • minElementIndex = 2
    • previousIndex = 1
    • countSubarrays = (2 - 1) * (5 - 2) = 1 * 3 = 3
    • result = (16 + 2 * 3 % MOD) % MOD = 22
  • Pop 1:
    • minElementIndex = 1
    • previousIndex = -1
    • countSubarrays = (1 - (-1)) * (5 - 1) = 2 * 4 = 8
    • result = (22 + 1 * 8 % MOD) % MOD = 30
• Push 5 to the stack.
• stack = [5]
• Final result = 30

Final Output

The final result is 30, which is the sum of all minimum values of the subarrays in the array [3, 1, 2, 4, 5].

Code