Show problems as
Classic problem #3507EasyArrayHash TableLinked ListHeap (Priority Queue)SimulationDoubly-Linked ListOrdered Set

Minimum Pair Removal to Sort Array I

Real-world version: Merging the Smallest Neighbouring Pair Until the Strip Rises
Tracked in this browser only
Read Minimum Pair Removal to Sort Array I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_pair_removal(readings: list[int]) -> int:
Java
public int minimumPairRemoval(int[] readings)

More on the same topics