Problem 907

(Last updated: )

Question statement

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.$ (contigious is not a typo)
Example: The contigious subarrays of [1,3,4,5] are [1], [3], [4], [5], [1,3], [3,4], [4,5], [1,3,4], [3,4,5], [1,3,4,5].

Solution

Disclaimer: I wrote two O($n^2$) solutions for this problem (one was space and slightly time optimized, and the other wasn’t), both of which ended up getting TLE-d. I was unable to find the optimization before the day was over, although (after checking the solutions from other people) in my second attempt it looked like I got close to the correct idea. So this was ultimately a failed challenge - but I will still write about my slow solution first and then talk explain the optimization using this trick called a monotonic stack.

Main idea:

Brute force:

The brute force approach is pretty straightforward. Just do a double loop with the outer loop index i being the right end of the contigious subarray and the inner loop index j being the left end. Finally compute min(arr[j:i+1]) and add it to sum. The min computation runs in O(n) time, so putting everything together, this is has a time complexity of O($n^3$).

DP approach 1:

With a DP approach, we can turn this to an O($n^2$) time complexity and O($n^2$) space complexity. To do this, we initialize a 2-d dp array initialzied to all zeroes, with the intention to store in dp[i][j] the minimum of arr[i][j+1]. One can do this O($n^2$) fashion by having two loops with the outer index $i$ and inner index $j$, and comparing arr[i] to dp[i-1][j], and setting
$$\texttt{dp[i][j]} = \begin{cases} \texttt{dp[i-1][j]} & \texttt{arr[i]} \geq \texttt{dp[i-1][j]} \ \texttt{arr[i]} & \texttt{arr[i]} < \texttt{dp[i-1][j]}\end{cases} $$
Then after each assignment is made, we add dp[i][j] to sum, and return sum.

DP approach 1.5:

One way to space optimize this is to realize we only ever access row dp[i-1] when scanning index i. So instead of a 2d dp array, we can get away with a 1d dp array, which stores the min values of the previous iteration. In the current iteration, we can then simply have a temp array that does the comparisons with dp, and at the end of the inner loop, we can redefine dp with temp, and reset temp to empty.

DP approach 2:

Since I kept getting TLE for this I opted for an approach that kept track of the absolute minimum value encountered so far. If arr[i] is smaller than or equal to the current absolute minimum, then arr[i] is going to be the smallest element of all contigious subarrays ending at i, which there are i+1 of, and thus sum+= i+1 $\times$ arr[i]. On the other hand if arr[i] is greater than the current absolute minimum, then we just do what we did in DP approach 1.5

Final correct approach (not mine):

By this time, I had given up hopes on solving this problem and looked at the possible solutions of others, when I realized that my solution came rather close to the actual solution. They key difference is that we can do the absolute minimum trick for all terms (not just the absolute minimum). We can have a stack of indices i such that the corresponding elements in arr are always arranged in ascending order. This way if arr[i] is smaller than every element in the stack, then sum gets incremented by arr[i]$\times$(i+1). Otherwise, we pop elements from the stack until we get to a point where arr[i] is greater than stack[arr[-1]], then stack[arr[-1]] is the minimum for all the contigious arrays corresponding to those that exist between [stack[-1], i], and thus we increment our sum by (i-stack[-1])$\times$stack[arr[-1]]. Finally we add i to the stack and continue.

This idea is still relatively new to me, so while I kinda understand what is going on, I need to sit and think about this deeply before I feel comfortable writing my own monotonic stacks.

Code:

Brute force:

1
2
3
4
5
6
7
8
def sumSubarrayMins(self, arr: List[int]) -> int:
    # Brute-force
    n=len(arr)
    sum=0
    for i in range(n):
        for j in range(i,n):
            sum += min(arr[i:j+1])
    return sum % (7+10**9)

DP ver 1.5:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def sumSubarrayMins(self, arr: List[int]) -> int:
    n = len(arr)
    dp = [0]
    sum = 0
    for i in range(n):
        temp = [0 for _ in range(i+1)]
        for j in range(i+1):
            if(i==j):
                temp[j] = arr[i]
            elif(arr[i] <= dp[j]):
                temp[j] = arr[i]
            else:
                temp[j] = dp[j]
            sum+=temp[j]
        dp = temp
    return sum % (7+10**9)

DP ver 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def sumSubarrayMins(self, arr: List[int]) -> int:
    n = len(arr)
    dp = []
    sum = 0
    abs_min = float('inf')
    for i in range(n):
        if(arr[i] <= abs_min):
            abs_min = arr[i]
            sum += arr[i]*(i+1)
            dp = [abs_min for _ in range(i+1)]
            continue

        temp = [0 for _ in range(i+1)]
        for j in range(i+1):
            if(i==j):
                temp[j] = arr[i]
            elif(arr[i] <= dp[j]):
                temp[j] = arr[i]
            else:
                temp[j] = dp[j]
            sum+=temp[j]
        dp = temp
    return sum % (7+10**9)

Final version (not mine):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def sumSubarrayMins(self, arr: List[int]) -> int:
    #Use DP & Montonic Stack
    n=len(arr)
    mod=10**9+7
    dp=[0 for _ in range(n)]
    s=[]
    ans=0
    for i in range(n):
        while len(s)>0 and arr[i]<= arr[s[-1]]:
            s.pop()
        if len(s)>0:
            j=s[-1]
            dp[i]=dp[j]+arr[i]*(i-j)
        else:
            dp[i]=arr[i]*(i+1)
        s.append(i)
        ans=(ans+dp[i])%mod
    return ans

Comments:

Time complexity: O(n) on average for the right solution, with worst case O($n^2$) if the stack gets really long.

Comments: No runtime for this problem, since none of my solutions got accepted.