0700HardArrayStackMonotonic StackPrefix Sum

Total Yield of Every Turbine Stretch

Tracked in this browser only

Trains the technique from

LeetCode 2281Sum of Total Strength of Wizards

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A wind farm has its turbines standing in a single row. rating[i] is the output rating of the turbine at position i.

A stretch is any non-empty run of turbines at consecutive positions. The yield of a stretch is the smallest rating inside it multiplied by the total of all ratings inside it.

Audit every stretch of the row and return the sum of their yields. Stretches are identified by the positions they cover, so two stretches covering different positions are both counted even when their ratings happen to match.

The sum grows far past machine word size, so return it modulo 1000000007.

Examples

Example 1

Input: rating = [7, 3, 8]
Output: 239

The six stretches yield `7*7 = 49`, `3*3 = 9`, `8*8 = 64`, `3*10 = 30`, `3*11 = 33` and `3*18 = 54`, and those add up to 239, which is already below the modulus.

Example 2

Input: rating = [6, 6, 2, 9]
Output: 375

The four single-turbine stretches yield 36, 36, 4 and 81. The adjacent pairs yield `6*12 = 72`, `2*8 = 16` and `2*11 = 22`, the triples yield `2*14 = 28` and `2*17 = 34`, and the whole row yields `2*23 = 46`. The total is 375.

Example 3

Input: rating = [1000000000, 1, 1000000000]
Output: 74

The two outer turbines each yield `1000000000 * 1000000000` on their own, the middle one yields 1, and the three stretches that include the middle turbine yield `1 * 1000000001`, `1 * 1000000001` and `1 * 2000000001`. The exact total is 2000000004000000004, and the answer is that value modulo 1000000007.

Constraints

1 <= rating.length <= 10^5
1 <= rating[i] <= 10^9
Return the sum of all stretch yields modulo 1000000007.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def total_stretch_yield(rating: list[int]) -> int:

Java

public int totalStretchYield(int[] rating)

The intended approach

Time O(n) for a row of n turbines: two cumulative passes and one stack pass, each position pushed and popped once.Space O(n) for the two cumulative tables and the stack.

Charge each stretch to the position holding its smallest rating, breaking a tie in favour of the leftmost such position, so every stretch is charged exactly once. A monotonic stack of strictly increasing ratings gives each position `j` the open interval `(left, right)` of positions it dominates: `left` is the nearest position to its left with a strictly smaller rating and `right` the nearest to its right with a rating no larger. Summing the rating totals of every stretch that starts in `(left, j]` and ends in `[j, right)` collapses to a fixed combination of prefix sums of the prefix sums, so each position costs O(1) once the two cumulative tables are built.

Pythonentry point: total_stretch_yield

MOD = 1000000007


def total_stretch_yield(rating):
    # O(n) time: one monotonic-stack pass over the row, with prefix sums of the
    # prefix sums so the ratings of every start/end pair are summed in O(1).
    n = len(rating)
    pre = [0] * (n + 1)              # pre[k] = rating[0] + ... + rating[k-1]
    for i in range(n):
        pre[i + 1] = (pre[i] + rating[i]) % MOD
    acc = [0] * (n + 2)              # acc[k] = pre[0] + ... + pre[k-1]
    for k in range(n + 1):
        acc[k + 1] = (acc[k] + pre[k]) % MOD

    total = 0
    stack = []                       # indices, ratings strictly increasing
    for i in range(n + 1):
        while stack and (i == n or rating[stack[-1]] >= rating[i]):
            j = stack.pop()
            left = stack[-1] if stack else -1
            right = i
            # j is the smallest rating of every stretch that starts in
            # (left, j] and ends in [j, right); ties break to the right.
            ends = (acc[right + 1] - acc[j + 1]) % MOD
            starts = (acc[j + 1] - acc[left + 1]) % MOD
            span = ((j - left) * ends - (right - j) * starts) % MOD
            total = (total + rating[j] % MOD * span) % MOD
        stack.append(i)
    return total % MOD

The obvious version

Walk every start position and extend the stretch one turbine at a time, carrying the running smallest rating and the running total, adding their product for each stretch. Quadratic in the row length but assumes nothing about which position owns a stretch.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_total_stretch_yield(rating):
    n = len(rating)
    total = 0
    for a in range(n):
        low = rating[a]
        run = 0
        for b in range(a, n):
            if rating[b] < low:
                low = rating[b]
            run += rating[b]
            total += low * run
    return total % 1000000007

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in