We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Subarray Minimums

Difficulty: Medium

Problem Description

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.

Key Insights

  • Every element in the array can serve as the minimum value for several subarrays.
  • The number of subarrays for which an element is the minimum can be calculated using the concept of previous and next smaller elements.
  • A monotonic stack can be utilized to efficiently determine the previous and next smaller elements for each element in the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a monotonic stack to find the number of subarrays for which each element is the minimum. We will calculate the distance to the nearest smaller element on the left and right for each element. The product of these distances gives the count of subarrays where the element is the minimum. We then multiply this count by the element value and accumulate the results.

  1. Use a stack to find the previous smaller element for each element in the array.
  2. Use another stack to find the next smaller element for each element in the array.
  3. For each element, calculate the contribution to the sum based on the number of subarrays it is the minimum for.
  4. Return the total sum modulo 10^9 + 7.

Code Solutions

def sumOfSubarrayMinimums(arr):
    MOD = 10**9 + 7
    n = len(arr)
    stack = []
    left = [0] * n
    right = [0] * n

    # Find previous smaller element indices
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    
    # Find next smaller element indices
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    result = 0
    for i in range(n):
        result += arr[i] * (i - left[i]) * (right[i] - i)
        result %= MOD

    return result
← Back to All Questions