Leetcode 907 explainer (for Recurse Center)

lc_907_explainer.md

import math


class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        spanned_indices = [[1,1] for _ in range(n + 1)]
        mono_i_stack = []
        for i, num in enumerate(arr + [-math.inf]):
            span = 0
            while mono_i_stack and mono_i_stack[-1][1] > num:
                j, _ = mono_i_stack.pop()
                spanned_indices[j][1] += span
                span += spanned_indices[j][0]
            spanned_indices[i][0] += span
            mono_i_stack.append((i, num))

        result = sum(l * r  * arr[i] for i, [l, r] in enumerate(spanned_indices[:n]))
        return result % ((10 ** 9) + 7)

First, a couple of observations:

• The number of subarrays/substrings in an array is always $O(n^2)$: any subarray is defined by two indices comprising the ends of the given subarray, so if $n$ is the length of the array, the number of subarrays is in one-to-one correspondence with the number of ways to select 2 items (indices, for our purposes) from $n$ choices, or $\binom{n}{2} = \frac{n(n-1)}{2} = O(n^{2})$.
• Even if we could get the minimums for each subarray in $O(1)$ time, we'd still need to do at least $O(n^{2})$ work just to enumerate all subarrays.
• Alternatively, we could consider the perspective from any index $i$ -- how many subarrays does $i$ participate in? Let's call this the participation count for index $i$, $p_i$.
• Notice that $p_i = (i + 1)(n - i)$. This is because we have $(i +1)$ choices for the left bound defining a subarray (including just $i$ itself) and $(n - k)$ choices for the right bound (including just $i$ itself). Any subarray defined by a choice of left and right bounds in this way necessarily spans (or includes) index $i$!
• But we don't really care about all the subarrays $i$ participates in...just the ones wherein it is the minimum! Let's call this $p_{i}^{\ast}$.
  • Why do we care about this? Because if we know how many subarrays for which any $i$ is the minimum, it will contribute $p_{i}^{\ast} \times A[i]$ (where $A$ is the input array) to the overall sum!

Great! Now how do we go about finding $\lbrace p_{i}^{*} \mid i \in \lbrace 0, 1, \ldots, n -1 \rbrace \rbrace$?

• We can use a monotonically increasing stack to calculate, for each index $i$, the number of indices (inclusive of $i$ itself) to the left of $i$ (spanning_indices[i][0]) and to the right of $i$ (spanning_indices[i][1]) that can serve as bounds for subarrays spanning $i$ where $A[i]$ is the minimum for those subarrays.
  • Initially, every index $i$ has a left and right span of $1$ because at the very least it is the minimum for $1 \times 1 = 1$ subarrays (namely, the subarray only containing $A[i]$).
  • We update the left span of an element at $i$ (spanning_indices[i][0]) whenever it enters the stack; we update the right span (spanning_indices[i][1]) when it leaves the stack.
  • The tricky bits are figuring out how to do the bookkeeping to enable the bullet point above:
    • span is a variable that will accumulate the number of spanned indices; whenever we pop an element from the stack, the number of spanned indices of popped element contributes to span.
    • Since the element being pushed onto the stack is smaller than the popped elements, we want to accumulate to contributions of the popped elements in span so we can update the total left span for the newly pushed element once the popping has finished: spanned_indices[i][0] += span).
    • But (on each iteration of the while loop maintaining the monotonic increasing invariant) span is ALSO the right span for the popped element, so we can update the popped element's right span: spanned_indices[j][1] += span.
    • We do this bookkeeping over all $n$ elements in the array in linear time since each element is only ever touched twice, i.e., $O(1)$ work per element.
  • The concatenation of -math.inf to the end of the input is just to force the stack to be cleared and the requisite bookkeeping to be performed on the elements in the stack once the for loop is complete.
• Once we have the spanning indices for each index, we use the same principle we used to calculate $p_i$ to calculate $p_{i}^{\ast}$, i.e., multiply the left and right spans for each index $i$ to give the number of subarrays wherein the element at index $i$ is the minimum.
• Our final answer is $\sum\limits_{i=0}^{n-1} p_{i}^{\ast} \times A[i]$ (modulo a big prime number given in the problem spec).