Contribution By Boundary

When To Use

Use this when summing over all subarrays and each element contributes as the minimum or maximum over some range.

Template

for each i:
    left = previous boundary where nums[i] stops being the extreme
    right = next boundary where nums[i] stops being the extreme
    contribution = nums[i] * count_of_subarrays_containing_i_inside_bounds

Duplicates need asymmetric comparisons: include equals on one side and exclude equals on the other.

Problems

Sum of Subarray Minimums

Problem: sum the minimum value of every subarray.

Pattern: contribution as minimum.

Applied pseudocode:

left[i] = previous index with value < nums[i]
right[i] = next index with value <= nums[i]
 
for i = 0; i < n; i++:
    choices_left = i - left[i]
    choices_right = right[i] - i
    ans += nums[i] * choices_left * choices_right

Subarray Ranges

Problem: sum max - min over every subarray.

Pattern: contribution as max minus contribution as min.

Min + Max Over Subarrays of Length At Most K

Problem: sum min and max over all subarrays with length at most k.

Pattern: contribution with capped left/right choices.

Total Strength of Wizards

Problem: sum min(subarray) * sum(subarray) over every subarray.

Pattern: minimum contribution plus prefix-of-prefix sums.