Sum of Subarray Minimums

IF
AlgoAxiomStaff Engineers
JSTS
Medium20 mins

Given an array of integers arr, find the sum of min(b) for every contiguous subarray b of arr. Since the answer may be large, return it modulo 10^9 + 7.

Examples

Input: arr = [3,1,2,4]

Output: 17

Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum = 17.

Input: arr = [11,81,94,43,3]

Output: 444

Explanation: The sum of all subarray minimums is 444.

Input: arr = [1,1,1]

Output: 6

Explanation: Subarrays are [1], [1], [1], [1,1], [1,1], [1,1,1]. All minimums are 1. Sum = 6 × 1 = 6.

Constraints

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4
Source: Monotonic Stack pattern — AlgoAxiom
JavaScript
Test Case 1
root = [1, 2, 3]
Test Case 2
root = [1, 2, 3, 4, 5]
Idle