algoadvance

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.

Clarifying Questions

  1. Input constraints:
    • What are the length boundaries for the input array arr?
    • What are the possible value ranges for the integers in arr?
  2. Output:
    • Is the result required modulo 10^9 + 7?

Strategy

  1. Understanding the Problem:
    • We need to find the minimum value of every subarray and then compute the sum of these minimum values. Directly iterating over all subarrays would be too slow as it results in O(n^3) complexity.
  2. Optimized Approach:
    • Utilize the concept of “Next Less Element” (NLE) and “Previous Less Element” (PLE) for each element in the array. This helps in determining the span of each element being the minimum in subarrays.
    • Use a monotonic stack to efficiently compute NLE and PLE for each element.
  3. Algorithm Steps:
    • Create two arrays PLE and NLE where:
      • PLE[i] represents the number of contiguous subarrays ending at arr[i] where arr[i] is the minimum.
      • NLE[i] represents the number of contiguous subarrays starting at arr[i] where arr[i] is the minimum.
    • For each element in arr, the count of subarrays where the element is minimum is PLE[i] * NLE[i].
    • Compute the sum using these counts and return the result modulo 10^9 + 7.

Code

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    
    # Arrays to store previous less and next less
    PLE = [0] * n
    NLE = [0] * n
    
    # Monotonic stack for Previous Less Element (PLE)
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        PLE[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    
    # Clear stack for reuse
    stack = []
    
    # Monotonic stack for Next Less Element (NLE)
    for i in range(n-1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        NLE[i] = n - i if not stack else stack[-1] - i
        stack.append(i)
    
    # Calculate the result
    result = 0
    for i in range(n):
        result = (result + arr[i] * PLE[i] * NLE[i]) % MOD
    
    return result

# Example Usage:
arr = [3, 1, 2, 4]
print(sumSubarrayMins(arr))  # Output: 17

Time Complexity

By exploiting the properties of the stack and the arrays PLE and NLE, we can efficiently compute the result while avoiding the brute-force O(n^3) approach.

Try our interview co-pilot at AlgoAdvance.com