Show problems as
Classic problem #2035HardArrayTwo PointersBinary SearchDynamic ProgrammingBit ManipulationMeet in the MiddleSortingOrdered SetBitmask

Partition Array Into Two Arrays to Minimize Sum Difference

Real-world version: Balanced Pontoon Ballast
Tracked in this browser only
Read Partition Array Into Two Arrays to Minimize Sum Difference on LeetCode(opens in a new tab)

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

A survey barge is trimmed by hanging ballast blocks under its two pontoons. The array blocks carries one trim value per block on board, and there are 2 * n blocks in all. A positive value weighs its pontoon down; a negative value lifts it.

The rigging crew has to hang every block, and each pontoon must finish with exactly n of them under it. The trim of a pontoon is the sum of the values hung under it. Return the smallest gap the crew can leave between the trims of the two pontoons, where the gap is an absolute value and so never negative.

Examples

Example 1

Input
blocks = [8, -2, 5, 1]
Output
0

One pontoon takes the blocks valued 8 and -2 for a trim of 6; the other takes 5 and 1, also a trim of 6. Both pontoons carry two blocks and the gap is 0.

Example 2

Input
blocks = [1, 1, 1, 9]
Output
8

Two blocks hang under each pontoon: 1 and 1 read as a trim of 2, and 1 and 9 read as a trim of 10, so the gap is 8.

Example 3

Input
blocks = [-7, 4, -3, 6, 0, -1]
Output
1

Three blocks per pontoon. Hanging -7, 6 and 0 on one side gives a trim of -1, and 4, -3 and -1 on the other gives a trim of 0, so the gap is 1.

Constraints

  • 1 <= n <= 15
  • blocks.length == 2 * n
  • -10^7 <= blocks[i] <= 10^7
  • Every block is hung, and each pontoon carries exactly n blocks

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 min_trim_gap(blocks: list[int]) -> int:
Java
public int minTrimGap(int[] blocks)

More on the same topics