Sum of Subarray Minimums

Sum of Subarray Minimums

What is this problem about?

The "Sum of Subarray Minimums interview question" is a medium-to-hard difficulty problem that requires finding the sum of the minimum elements of every possible contiguous subarray within a given array. Because the number of subarrays is O(N^2), a brute-force approach that finds the minimum of each subarray is O(N^3) or O(N^2), which is insufficient for large arrays.

The goal is to find a way to count how many subarrays a particular element is the minimum of. If an element x at index i is the minimum for K different subarrays, it contributes x * K to the total sum.

Why is this asked in interviews?

Companies like Google, Amazon, and Meta use this "Sum of Subarray Minimums coding problem" to test a candidate's mastery of the Monotonic Stack. It evaluates:

1. Optimization Skills: Moving from a quadratic solution to a linear one.
2. Stack Applications: Using a stack to maintain elements in a specific order (increasing or decreasing).
3. Combinatorics: Calculating the number of subarrays based on left and right boundaries.
4. Boundary Management: Handling duplicate elements carefully so they aren't counted multiple times.

Algorithmic pattern used

The core "Monotonic Stack interview pattern" is used here. For each element arr[i], we need to find:

• The nearest element to the left that is smaller than arr[i]. Let this be at index L.
• The nearest element to the right that is smaller than arr[i]. Let this be at index R.

The number of subarrays where arr[i] is the minimum is (i - L) * (R - i). A monotonic stack allows us to find these "Nearest Smaller Values" for all elements in O(N) time.

Example explanation

Consider the array [3, 1, 2, 4]. For the element 1 at index 1:

• To the left, there are no smaller elements. Boundary L = -1. Distance = 1 - (-1) = 2.
• To the right, there are no smaller elements. Boundary R = 4. Distance = 4 - 1 = 3. Number of subarrays where 1 is the minimum is 2 * 3 = 6. Those subarrays are: [3, 1], [1], [1, 2], [1, 2, 4], [3, 1, 2], [3, 1, 2, 4]. The contribution to the sum is 1 * 6 = 6.

Common mistakes candidates make

• Double Counting Duplicates: If the array has duplicate numbers like [2, 1, 2], you must decide whether the left or right search is "strictly less" vs "less than or equal". If both are "strictly less", you might miss subarrays; if both are "less than or equal", you will double-count.
• Modulo Operations: The result can be very large, so you must apply modulo 10^9 + 7 at each addition step to avoid overflow.
• Stack Implementation: Forgetting to clear the stack or handle the empty stack case (which represents reaching the end of the array).

Interview preparation tip

The "Monotonic Stack interview pattern" is a high-ROI topic. It is used in several "Stack interview questions" like "Largest Rectangle in Histogram" and "Trapping Rain Water". If you see a problem involving "nearest smaller" or "nearest larger" elements, a monotonic stack is almost always the answer. Practice the logic of calculating (i - L) * (R - i) as it appears frequently in subarray-related combinatorics.