Editor

Sum of Subarray Minimums

#170 · Stacks and queues · Advanced · 165 XP · about 35 min

A subarray is a run of one or more neighbouring items from a list. Write sum_of_minimums(nums) that looks at every subarray of nums, takes the smallest value in each one, and returns the total of all those minimums.

Examples

sum_of_minimums([2, 4, 1])  # returns 11
sum_of_minimums([5, 5])     # returns 15
sum_of_minimums([1, 2, 3])  # returns 10
sum_of_minimums([])         # returns 0

For [2, 4, 1] the subarrays are [2], [4], [1], [2, 4], [4, 1] and [2, 4, 1]. Their minimums are 2, 4, 1, 2, 1 and 1, which add up to 11.

Constraints

  • 0 <= len(nums) <= 30,000
  • -10,000 <= nums[i] <= 10,000
  • A list of 30,000 items has about 450 million subarrays, so visiting them one by one is far too slow.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.