Pattern visualizer
Sum of Subarray Minimums
Listing every subarray is quadratic before you even look at it, so flip the question around: instead of asking each subarray for its minimum, ask each element how many subarrays it is the minimum of. An element owns exactly the stretch between the nearest smaller element on its left and the nearest smaller on its right — pick any left end inside that stretch and any right end, and it is the smallest thing in between. That makes its count a simple product of two distances. A monotonic increasing stack of indices finds both boundaries in one pass: the moment a smaller value arrives, every stacked element bigger than it has just met its right boundary, and whatever sits below it on the stack is its left boundary. Duplicates are the one trap — pop on >= so equal values break leftwards, or a subarray whose minimum appears twice gets counted twice. Animated on: arr = [3, 1, 2, 4, 3, 1] — add up the minimum of every one of its 21 contiguous subarrays. Answer: 33..
Monotonic increasing stack, counting who owns each subarray
arr = 3, 1, 2, 4, 3, 1, with a 0 pinned on at index 6 that is smaller than everything so every real element gets forced off the stack and paid for. Instead of listing all 21 subarrays, ask of each element: how many subarrays is IT the minimum of? Multiply that count by its value and add up.
1FUNCTION sumSubarrayMins(A):2 APPEND 0 TO A3 stack <- [-1]4 total <- 05 FOR i <- 0 TO LENGTH(A) - 1:6 WHILE TOP(stack) != -1 AND A[TOP(stack)] >= A[i]:7 j <- POP(stack)8 total <- total + A[j] * (j - TOP(stack)) * (i - j)9 PUSH i ONTO stack10 RETURN total
← / → step · space play · Home restart