Compute the sum of the minimum value of every contiguous subarray.
Given an integer array, consider every contiguous subarray and take the minimum element from that subarray. Return the sum of all these minimum values.
Because the result can be very large, compute it modulo .
This problem is about counting how many subarrays use each element as the minimum, instead of checking every subarray one by one.
Input Format
- An integer array
arrof lengthn. - Each element is an integer.
Output Format
- Return a single integer: the sum of the minimum element of every contiguous subarray, modulo .
Constraints
- Values can be positive, zero, or negative depending on the variant, but the standard interview formulation uses integers in a moderate range.
- A correct solution should be better than .
- Use modulo for the final answer.
Example 1
Input
arr = [3, 1, 2, 4]
Output
17
Explanation
The subarrays and their minimums are:
- [3] -> 3
- [1] -> 1
- [2] -> 2
- [4] -> 4
- [3,1] -> 1
- [1,2] -> 1
- [2,4] -> 2
- [3,1,2] -> 1
- [1,2,4] -> 1
- [3,1,2,4] -> 1
Sum = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17.
Example 2
Input
arr = [11, 81, 94, 43, 3]
Output
444
Explanation
Each subarray minimum contributes to the total. Counting contributions by element yields a total of 444.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.