PPractick

The problem

A risk engine scores a price series by summing, over every contiguous window, the lowest price in that window, reported modulo 10⁹ + 7. There are O(n²) windows, so enumerating them is too slow for n = 3·10⁴. Flip the question: for each element, in how many windows is it the minimum? It is the minimum of windows that start after the previous smaller element and end before the next smaller element. Monotonic stacks find those boundaries in O(n), and the contribution is a[i] × (#choices of start) × (#choices of end).

Example: [3, 1, 2, 4] → 17.

Function signature

int sumSubarrayMins(const vector<int>& arr);  // modulo 1e9 + 7

Test cases

Input	Output	Explanation
[3, 1, 2, 4]	17	3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1
[11, 81, 94, 43, 3]	444
[1, 2, 3]	10
[2, 2, 2]	12	6 windows, each with minimum 2; ties must be counted once
[1]	1

(Confirm: every non-empty contiguous subarray counts once; values are positive; the result is taken modulo 1,000,000,007.)

How interviewers phrase it

• "Given an array of integers, find the sum of min(b) over every contiguous subarray b, modulo 10⁹ + 7" (LeetCode 907).

Clarifying questions to ask

1. Contiguous subarrays only? (Yes.)
2. How large is n? (Up to 3·10⁴, so O(n²) is borderline and O(n) is expected.)
3. Can there be duplicates? (Yes, and they need careful tie handling.)

Follow-ups to expect

1. "How many subarrays have a[i] as their minimum?"
2. "How do you avoid double counting with duplicates?"
3. "How are the boundaries found?"
4. "What about the sum of subarray maximums?"
5. "Complexity?"

Related questions

• Next Greater Element Medium
• Next Greater Element - 2 Medium
• Next Smaller Element Medium
• Sum of Subarray Ranges Medium
• Number of Greater Elements to the Right Easy
• Largest rectangle in a histogram Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in