0702HardArrayBinary SearchGreedySortingPrefix Sum

Regrading the Survey Pegs

Tracked in this browser only

Trains the technique from

LeetCode 2448Minimum Cost to Make Array Equal

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 survey crew has driven a row of pegs into a slope. Peg i currently sits at height height[i] centimetres, and moving that peg one centimetre costs effort[i] units of work whether it goes up or down.

The crew now has to bring every peg to one shared height. They may pick any whole number of centimetres as that shared height, and each peg may be moved by any whole number of centimetres.

Return the least total work that levels all the pegs.

Examples

Example 1

Input: height = [12, 9, 20, 9], effort = [5, 2, 1, 3]
Output: 23

Levelling everything to height 12 moves the first peg not at all, both pegs at height 9 up by 3 and the peg at height 20 down by 8, for `2*3 + 3*3 + 1*8 = 23` units of work.

Example 2

Input: height = [4, 7, 11, 16, 21], effort = [1, 1, 1, 1, 40]
Output: 46

Levelling everything to height 21 leaves the last peg alone and raises the other four by 17, 14, 10 and 5 centimetres at one unit of work per centimetre, for 46 units in total.

Example 3

Input: height = [6, 6, 6], effort = [9, 2, 5]
Output: 0

The pegs already share a height, so nothing has to move.

Constraints

1 <= height.length <= 10^5
height.length == effort.length
1 <= height[i], effort[i] <= 10^6
The pegs are laid out so that the answer is at most 10^15.

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 least_regrade_work(height: list[int], effort: list[int]) -> int:

Java

public long leastRegradeWork(int[] height, int[] effort)

The intended approach

Time O(n log n) for n pegs, dominated by sorting them by height; the two sweeps are linear.Space O(n) for the sorted height-effort pairs.

Total work as a function of the shared height is a sum of absolute-value terms, each scaled by that peg's effort, so it falls while more than half of the total effort sits above the chosen height and rises once more than half sits below it. Pair each height with its effort, sort by height, and sweep forward adding efforts until the running total first reaches half of the overall effort, rounded up; that peg's height is the level to use. A second sweep adds up each peg's distance to it times its effort.

Pythonentry point: least_regrade_work

def least_regrade_work(height, effort):
    # O(n log n): sort the pegs by height, then walk the sorted order adding up
    # effort until at least half of the total effort has been passed. That peg's
    # height is the level to move everything to; one more pass totals the work.
    pegs = sorted(zip(height, effort))
    total_effort = 0
    for w in effort:
        total_effort += w
    half = (total_effort + 1) // 2
    run = 0
    level = pegs[0][0]
    for h, w in pegs:
        run += w
        if run >= half:
            level = h
            break
    work = 0
    for h, w in pegs:
        work += w * abs(h - level)
    return work

The obvious version

Try every whole height from a little below the lowest peg to a little above the highest, add up the work each one would need, and keep the smallest total. Costs one full pass per candidate height, so it is only usable when the pegs sit close together.

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_least_regrade_work(height, effort):
    lo = min(height)
    hi = max(height)
    best = None
    for level in range(lo - 3, hi + 4):
        work = 0
        for h, w in zip(height, effort):
            work += w * abs(h - level)
        if best is None or work < best:
            best = work
    return best

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