LeetCode 907 Sum of Subarray Minimums - Example and Complexity Analysis

Trace [3, 1, 2, 4].

Compute left boundaries (previous smaller element):

• arr[0]=3: no smaller to left. left[0] = -1.
• arr[1]=1: no smaller to left. left[1] = -1.
• arr[2]=2: arr[1]=1 is smaller. left[2] = 1.
• arr[3]=4: arr[2]=2 is smaller. left[3] = 2.

Compute right boundaries (next smaller element):

• arr[0]=3: arr[1]=1 is smaller. right[0] = 1.
• arr[1]=1: no smaller to right. right[1] = 4.
• arr[2]=2: no smaller to right. right[2] = 4.
• arr[3]=4: no smaller to right. right[3] = 4.

Contributions: 3×(0-(-1))×(1-0) = 3, 1×(1-(-1))×(4-1) = 6, 2×(2-1)×(4-2) = 4, 4×(3-2)×(4-3) = 4.

Sum = 3 + 6 + 4 + 4 = 17.

Two passes with monotonic stacks. $O(n)$ time. $O(n)$ space for boundary arrays.