Sum of Subarray Minimums | O(n) with Monotonic Stack | Dynamic Programming

In this video, we learn how to find the sum of subarray minimums using dynamic programming in linear time complexity. The solution uses monotonic stacks. We take an example, understand how to come up with an intuition and then deduce the dp formula together. At the end, we code the JavaScript solution together.

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr.

[badalrooprai]

very well articulated. I was struggling to understand this approach and was exploring it online; however, I got clarity only after watching your video. Thank you for explaining it. Keep up this good work.

[_saikatbanerjee]

Great explanation, everywhere there is solution with left subarray and right subarray .... But u have explained it with quite ease, hats off

[anmolag]

Great explaination. Now I understood how to approach the solution for this problem

[timhoward]

Your solution is better than all of the ones I have seen on LeetCode - and well explained. They all search to the left AND RIGHT for a smaller element, whereas you only use the left smaller element. I implemented your approach in C++ and got faster than 82% of other submissions. Do you know why these other solutions look for a lesser value on both sides of the current value? I can't figure out why all of these other solutions are doing extra or redundant work.

[tavinsingh]

"while(stack.length && arr[stack[stack.length - 1]] > arr[i]". How would this run if the stack it initialized empty and never get anything added to it until the while loop runs?

[fahdjamy]

When you say non-decreasing order, do you mean increasing order?