907.sum-of-subarray-minimums.md

907. Sum of Subarray Minimums

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

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 = 1000000000 + 7

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.