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<sup>9</sup> + 7.

Problem Statement

Given an array:

arr = [3, 1, 2, 4]

We want:

• all subarrays

• find the minimum in each

• sum them up

Subarrays:

[3]     min = 3
[3,1]   min = 1
[3,1,2] min = 1
[3,1,2,4] min = 1
[1]     min = 1
[1,2]   min = 1
[1,2,4] min = 1
[2]     min = 2
[2,4]   min = 2
[4]     min = 4

Sum = 17

Bruteforce Approach

Find all the possible subarrays and add the mins then return the sum.

Key Observation

Instead of asking:

What is the minimum of this subarray?

We ask:

For how many subarrays is arr[i] the minimum?

Because then:

answer=∑arr[i]×count(i)

Core Idea: Contribution Technique

Every element contributes as the minimum in some subarrays.

Example:

arr = [3, 1, 2, 4]

The element 1 is the minimum in:

[1]
[3,1]
[1,2]
[1,2,4]
[3,1,2]
[3,1,2,4]

That’s 6 subarrays.

So contribution of 1:

1×6=61 \times 6 = 61×6=6

Now do this for every element.

How to Count Subarrays Where arr[i] is Minimum?

We need to find:

• how far can we extend to the left?

• how far can we extend to the right?

Until a smaller element breaks the boundary.

Left boundary:

Nothing smaller than 1 exists to the left.

So it can extend fully.

Right boundary:

Nothing smaller exists to the right.

So it can extend fully.

---

So total subarrays where 1 is minimum:

leftCount×rightCountleftCount \times rightCountleftCount×rightCount

Code

var leftNextSmaller = function(arr, n){
    const map = new Map()
    let stack = []
    for(let i=0; i<n; i++){
        while(stack.length!==0 && arr[i]<arr[stack[stack.length-1]]){
            stack.pop()
        }
        if(stack.length===0){
            map.set(i, -1)
        }else{
            map.set(i, stack[stack.length-1])
        }
        stack.push(i)
    }
    return map
}

var rightNextSmaller = function(arr,n){
      const map = new Map()
    let stack = []
    for(let i=n-1; i>=0; i--){
        while(stack.length!==0 && arr[i]<=arr[stack[stack.length-1]]){
            stack.pop()
        }
        if(stack.length===0){
            map.set(i, arr.length)
        }else{
            map.set(i, stack[stack.length-1])
        }
        stack.push(i)
    }
    return map
}

var sumSubarrayMins = function(arr) {
    const MOD = 1000000007;
  let n = arr.length
  let leftMap = leftNextSmaller(arr, n)
  let rightMap = rightNextSmaller(arr,n)
  let sum = 0
  for(let i=0; i<n; i++){
    let leftEle = i- leftMap.get(i)
    let rightEle = rightMap.get(i) - i
    // sum = sum + (arr[i]*(leftEle*rightEle))
    let contribution = (arr[i] * leftEle * rightEle) % MOD;
        sum = (sum + contribution) % MOD;
  }
  return sum
};

Mod is used for handelling the bigger int sums. Otherwise the test case will be failed in bigger integer sums.

Complexity

Total:

O(n)

Space:

O(n)