1023EasyArrayHash TableLinked ListHeap (Priority Queue)SimulationDoubly-Linked ListOrdered Set

Merging the Smallest Neighbouring Pair Until the Strip Rises

Tracked in this browser only

Trains the technique from

LeetCode 3507Minimum Pair Removal to Sort Array I

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 strip of readings reads readings. While the strip still falls somewhere, meaning some reading sits below the one before it, do the following once:

among all pairs of neighbouring readings, take the pair whose two readings add to the least, and where several tie, take the leftmost of them;
replace that pair with a single reading holding their sum.

Return how many times this has to be done before the strip no longer falls anywhere.

Examples

Example 1

Input: readings = [4, 7, 3]
Output: 1

The strip falls at the last step. The two neighbouring pairs add to eleven and ten, so the later pair is the one merged, leaving 4 and 10, which never falls.

Example 2

Input: readings = [9, 8, 7, 6, 5]
Output: 4

The strip falls at every step. Each round merges the smallest neighbouring pair, and it takes four rounds before a single reading is left, which cannot fall.

Example 3

Input: readings = [-5, -3, -1]
Output: 0

The readings already climb, so nothing is merged.

Constraints

1 <= readings.length <= 50
-1000 <= readings[i] <= 1000

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

Java

public int minimumPairRemoval(int[] readings)

The intended approach

Time O(n^2) over the strip's starting length.Space O(n) for the working strip.

The rule leaves no room for choice, so the work is to carry it out faithfully and count. Each round turns two readings into one, so the strip shortens every time and there can be at most one round fewer than the strip's starting length; a strip down to a single reading never falls. A round is two walks. The first checks whether any reading sits below the one before it, and stops everything if none does. The second finds the neighbouring pair with the smallest sum, keeping the earliest whenever a later pair merely ties, and splices that pair into their sum. With at most fifty readings a plain walk per round is more than enough, and the number of rounds is the answer.

Pythonentry point: minimum_pair_removal

def minimum_pair_removal(readings):
    strip = list(readings)
    rounds = 0
    while True:
        falls = False
        for at in range(1, len(strip)):
            if strip[at] < strip[at - 1]:
                falls = True
                break
        if not falls:
            return rounds
        best = 0
        low = strip[0] + strip[1]
        for at in range(1, len(strip) - 1):
            here = strip[at] + strip[at + 1]
            if here < low:
                low = here
                best = at
        strip[best:best + 2] = [low]
        rounds += 1

The obvious version

Carry the rule out the same way but decide things by sorting rather than scanning. Test whether the strip falls by comparing it against a sorted copy of itself, and find the pair to merge by listing every neighbouring pair as its sum with its position, then sorting that list and taking the front of it, which puts the smallest sum first and the earliest position first among ties. Costs a sort per round rather than a walk.

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_minimum_pair_removal(readings):
    strip = list(readings)
    rounds = 0
    while strip != sorted(strip):
        pairs = []
        for at in range(len(strip) - 1):
            pairs.append((strip[at] + strip[at + 1], at))
        pairs.sort()
        total, at = pairs[0]
        strip = strip[:at] + [total] + strip[at + 2:]
        rounds += 1
    return rounds

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