medium Sum of Subarray Minimums

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 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

import java.util.Stack;

class Solution {

  public int sumSubarrayMins(int[] arr) {
    int MOD = 1_000_000_007;
    int n = arr.length;
    long result = 0; // Final sum of subarray minimums
    Stack<Integer> stack = new Stack<>();

    // Iterate through the array plus one extra iteration for a sentinel.

    for (int currentIndex = 0; currentIndex <= n; currentIndex++) {
      // If we reached the end, use 0 as a sentinel value; otherwise, use the current element.
      // It helps to process all remaining elements in the stack.
      int currentElement = (currentIndex == n) ? 0 : arr[currentIndex];

      // Process elements in the stack while the current element is smaller than the element at the top.
      // Here, we maintain monotonic increasing stack.
      while (!stack.empty() && arr[stack.peek()] > currentElement) {
        // Pop the index whose corresponding element is greater than currentElement.
        int minIndex = stack.pop();
        // Determine the previous index from the stack; if the stack is empty, use -1.
        int previousIndex = stack.empty() ? -1 : stack.peek();

        // Calculate the number of subarrays where arr[minIndex] is the minimum:
        // (minIndex - previousIndex) gives the count of subarrays ending at minIndex,
        // and (currentIndex - minIndex) gives the count of subarrays starting at minIndex
        // that can extend until currentIndex.
        int countSubarrays =
          (minIndex - previousIndex) * (currentIndex - minIndex);

        // Add the contribution of arr[minIndex] for these subarrays to the result.
        result = (result + ((long) arr[minIndex] * countSubarrays) % MOD) % MOD;
      }

      // Push the current index onto the stack for further processing.
      stack.push(currentIndex);
    }

    return (int) (result % MOD);
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] arr1 = { 3, 1, 2, 4, 5 };
    System.out.println("Example 1: " + solution.sumSubarrayMins(arr1));

    // Example 2
    int[] arr2 = { 2, 6, 5, 4 };
    System.out.println("Example 2: " + solution.sumSubarrayMins(arr2));

    // Example 3
    int[] arr3 = { 7, 3, 8 };
    System.out.println("Example 3: " + solution.sumSubarrayMins(arr3));
  }
}

Complexity Analysis

Time Complexity

• The algorithm iterates through the array arr once, which takes time.
• Inside the loop, each element is pushed and popped from the monotonic stack exactly once. Since each element is handled at most twice (once when pushed and once when popped), the total number of operations is at most 2n, which is .
• Thus, the overall time complexity of the algorithm remains .

Space Complexity

• The space complexity is dominated by the space required for the monotonic stack, which in the worst case, can hold all elements of the array. Therefore, in the worst case, the space complexity is .
• Apart from the stack, we only use a few integer variables, which take space.
• Hence, the overall space complexity is .