907.sum-of-subarray-minimums.md

907. Sum of Subarray Minimums

Monotonic Stack

Idea! We will find the smallest number and see how many time does the smallest number contribute to the sum of min(b) in the subarray.

Suppose we have a smallest number 2 in our array X X X X 2 X X X, we will find out that how many time does 2 contribute to the sum of min(b). We can keep looking at the left and right hand side until we find the number that is smaller than 2.

// Search the smaller number from left and right hand side
X X X X 2 X X X
  <-----*----->

// This is the range that the subarray contains 2 and contributes the min(b)
X X 0 3 2 4 5 1 
      |-*---|

We will keep looking for the previous and next smaller numbers. (prevSmaller, nextSmaller).

Then 2 contributes to the sum of min(b) from all the subarrays ranging from [3, 2, 4, 5] that contains 2, that is all the subarrays begin from [3, 2], end at [2, 4, 5], so there are 2 * 3 subarrays.

/// The possible start of subarray that contains 2.
[3, 2, _, _]

/// The possible end of subarray that contains 2.
[_, 2, 4, 5]

Pitfalls

1. What if we can't find the previous or next smaller number? We have to set -1 or n to indicate that there is no such number.

index -1, 0, 1, 2, 3, 4, 5, 6, 7
value     3  5  1  2  4  5  9
       |--------*--------------|

2. What if we have the same smallest number?

... 2 3 2 4 5 2 ...
    |---*-----|

There are duplicate 2 (leftmost and rightmost), which one contributes to min(b) in ..., 2 3 2 4 5 2, ...? To prevent duplicate calculation, we treat the first 2 the minimum number and ignore other duplicate 2, so we will stop looking for previous smaller if it's the same number, but we won't stop for next smaller.

...2 5 6 2 3 2 4 5 2 8 2 9 1
         |---*-------------|

Nice Explanation Video: https://www.youtube.com/watch?v=TZyBPy7iOAw

private val mod = 1_000_000_007

fun sumSubarrayMins(arr: IntArray): Int {
    val n = arr.size
    // Index, we have to provide the default value to indicate not found
    val nextSmaller = IntArray(n) { n }
    val prevSmaller = IntArray(n) { -1 }

    // Index, we have to calculate the length of subarray
    val stack = Stack<Int>()
    for (i in 0 until n) {
        while (stack.isNotEmpty() && arr[stack.peek()] > arr[i]) {
            val index = stack.pop()
            nextSmaller[index] = i
        }
        stack.push(i)
    }
    stack.clear()
    for (i in n -1 downTo 0) {
        // There is "equal" operator, we treat the first duplicate numbers as smaller number
        while (stack.isNotEmpty() && arr[i] <= arr[stack.peek()]) {
            val index = stack.pop()
            prevSmaller[index] = i
        }
        stack.push(i)
    }

    // Use Long type to prevent overflow
    var result = 0L
    for (i in 0 until n) {
        val sum: Long = arr[i].toLong() * (nextSmaller[i] - i).toLong() % mod * (i - prevSmaller[i]) % mod
        result = (result + sum) % mod
    }
    return result.toInt()
}

• Time Complexity:: O(n) to iterate the whole array and each element is pushed and popped at most once.
• Space Complexity:: O(n) for stack and arrays to store the previous and next smaller index.