Skip to content
RED SAGSkills
hard60 ptsstackarraysmath

Sum of Every Stretch Minimum

For every non-empty contiguous subarray of nums, take its minimum. Return the sum of all those minimums modulo 1000000007.

Example 1

Input: nums = [3, 1, 2, 4]
Output: 17
Explanation: Minimums: 3,1,2,4 / 1,1,2 / 1,1 / 1, totalling 17.

Example 2

Input: nums = [2, 2]
Output: 6

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • 1 <= nums[i] <= 3 * 10^4
Hint 1

Count, for each element, how many subarrays have it as their minimum.

Hint 2

Monotonic stacks give the distance to the previous smaller and next smaller element. Break ties on one side only so equal values are not double-counted.

Good practice for: Data Scientist, Data Engineer, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Backend Developer, Site Reliability Engineer

Run checks your code on 2 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.