0440MediumArrayStackMonotonic Stack

Total Swing Across Every Stretch

Tracked in this browser only

Trains the technique from

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 sailplane carries a barograph that writes down one altitude reading a minute for the whole flight. readings lists them in flight order, each in metres measured against the ridge line the pilot is working, so a reading taken below the ridge is negative.

A stretch is any run of one or more consecutive readings, identified by where it starts and where it ends. The swing of a stretch is its highest reading minus its lowest reading; a stretch holding a single reading therefore swings 0.

Return the sum of the swings of every stretch of readings. A flight of n readings has n * (n + 1) / 2 stretches, and the total can be far larger than a 32-bit integer holds, so it must be returned as a 64-bit value.

Examples

Example 1

Input: readings = [12, -5, 12, 30, -5]
Output: 279

The five single-minute stretches each swing 0. The four two-minute stretches swing 17, 17, 18 and 35, the three three-minute stretches swing 17, 35 and 35, the two four-minute stretches swing 35 and 35, and the whole flight swings 35, which adds up to the figure returned.

Example 2

Input: readings = [4, 4, 4, 4]
Output: 0

Every stretch, however long, has the same highest and lowest reading, so each one swings 0.

Example 3

Input: readings = [7]
Output: 0

A single reading forms the only stretch, and its highest and lowest reading are the same.

Example 4

Input: readings = [1000000000, -1000000000]
Output: 2000000000

There are three stretches: the two single readings swing 0 each, and the pair swings 2000000000, which is past what a 32-bit integer holds.

Constraints

1 <= readings.length <= 1000
-10^9 <= readings[i] <= 10^9

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_swing(readings: list[int]) -> int:

Java

public long totalSwing(int[] readings)

The intended approach

Time O(n): two sweeps, and each index is pushed and popped at most once per sweep.Space O(n) for the index stack.

Split the answer into the sum of every stretch's highest reading minus the sum of every stretch's lowest reading, and charge each of those sums to individual readings: a reading is the highest of exactly (steps back to the nearest reading that beats it) times (steps forward to the nearest reading that beats it) stretches. Both distances come out of one sweep with a stack of indices held in monotone order, run once for the highs and once for the lows. Ties are settled by using a strict comparison on one side and a loose one on the other so that every stretch is charged exactly once.

Pythonentry point: total_swing

def total_swing(readings):
    # A stretch contributes its highest reading and subtracts its lowest, so the
    # answer is (sum of every stretch's maximum) - (sum of every stretch's
    # minimum). Each reading can be charged for the stretches it dominates, and
    # the number of those is (distance back to the nearest reading that beats it)
    # times (distance forward to the nearest reading that beats it). A stack that
    # only ever holds indices in decreasing order of reading finds both distances
    # in one sweep; ties are broken by letting one side use a strict comparison
    # and the other a loose one, so no stretch is charged twice.
    # O(n) time, O(n) space for the stack.
    size = len(readings)
    total = 0
    stack = []
    for i in range(size + 1):
        while stack and (i == size or readings[stack[-1]] <= readings[i]):
            mid = stack.pop()
            left = stack[-1] if stack else -1
            total += readings[mid] * (mid - left) * (i - mid)
        if i < size:
            stack.append(i)
    stack = []
    for i in range(size + 1):
        while stack and (i == size or readings[stack[-1]] >= readings[i]):
            mid = stack.pop()
            left = stack[-1] if stack else -1
            total -= readings[mid] * (mid - left) * (i - mid)
        if i < size:
            stack.append(i)
    return total

The obvious version

Walk over every start and every end, slice out that stretch, and add its highest reading minus its lowest reading straight from built-in scans.

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_swing(readings):
    size = len(readings)
    total = 0
    for start in range(size):
        for end in range(start, size):
            window = readings[start:end + 1]
            total += max(window) - min(window)
    return total

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 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