Sum of Subarray Minimums - Miscellaneous / Monotonic Stack

Problems
1

https://algo.monster/problems/sum-of-subarray-minimums

2

The explanation here really needs some work…

3

It also has little similarity to the largest rectangle in a histogram problem (which I feel should be added here), except, instead of finding the largest one, just add them all up.

4

I copied and pasted your solution on LeetCode, and it did not pass one of the test cases, please verify your solution

5

very nice explanation here:
https://www.youtube.com/watch?v=lOfJfT-U_io

6

^

7

This question is terrible for the section. Why?

  1. Because of lack of tests, all the tests are green on my solution, which is not optimal, but you can not validate this since lack of tests (obviously my solution fails on LC tests, gives LTE); (but again, this problem not the 1st one);
  2. The section is about the monotonic stack technique, I don’t mind mixing it with other techniques, but give us more problems so we could polish it before actually thinking about which technique else might be added to solve this problem;
  3. The explanation is sux, mostly done because something needs to be here, no one tested the description. How to test it? The easiest way is to give a similar problem to anyone else who is preparing for Coding Interviews and check if that person could understand the problem, and solution and then solve it without help;
  4. No feedback/follow-up in comments, why bother if you have already bought it, right?

Honestly, before this problem, I felt it was me, hopeless and kinda stupid. Now I tend to think the descriptions here are so, so… quantity is over quality.

My failed N^2 solution

def sum_subarray(weights: List[int]) -> int:
    result = 0
    k = 1
        
    while k < len(weights) + 1:
        window = deque()
        l = 0
            
        for r in range(len(weights)):
            while window and weights[window[-1]] > weights[r]:
                window.pop()
                
            window.append(r)

            if r - l + 1 == k:
                result += weights[window[0]]
                if window[0] == l:
                    window.popleft()
                l += 1
        k += 1
        
    return result
8

Leetcode not passing? Don’t forget leetcode requires us to return the answer modulo 10^9 + 7

9

I am not sure it’s fair to say that the solution is incorrect, just because it does not pass the LeeCode problem, since LC has the large number constraint, and this problem does not. This solution would pass the LC check only if added the mod.

public static class Element {
    int count;
    int val;
    public Element(int count, int val) {
        this.count = count;
        this.val = val;
    }
}

public int sumSubarrayMins(int[] arr) {
    int sum = 0;
    Stack<Element> stack = new Stack<>();
    double mod = 1e9 + 7;
    long curSum = 0;
    for (int i=0; i < arr.length; i++ ) {
        int curValue = arr[i];
        int curCount = 1;
        while (!stack.empty()) {

            if (stack.peek().val < curValue) {
                break;
            }

            Element e = stack.pop();
            curCount += e.count;
            curSum -= e.val * e.count;
        }

        stack.push(new Element(curCount, curValue));
        System.out.println("currSum="   + curSum +
                           ",curValue=" + curValue +
                           ",curCount=" + curCount);
        curSum += curValue * curCount;
        sum += curSum;
        sum %= mod;
    }
    return (int)sum;
}

===

10

That being said, the solution explanation of AlgoMonster does leave a lot to be desired

11

agreed!