0226HardArrayTwo PointersBinary SearchDynamic ProgrammingBit ManipulationMeet in the MiddleSortingOrdered SetBitmask

Balanced Pontoon Ballast

Tracked in this browser only

Trains the technique from

LeetCode 2035Partition Array Into Two Arrays to Minimize Sum Difference

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

Python

def min_trim_gap(blocks: list[int]) -> int:

Java

public int minTrimGap(int[] blocks)

The intended approach

Time O(n * 2^n) for an input of 2n blocksSpace O(2^n) for the subset-sum buckets

Cut the manifest down the middle and enumerate every subset of each half, filing each subset sum in a bucket keyed by how many blocks it holds. A pontoon load is then one left-half subset plus one right-half subset whose block counts add up to n, and for a fixed left sum the gap is smallest when twice the combined sum sits nearest the total of all blocks. Sorting each right-half bucket lets a binary search locate that partner, and the two stored sums bracketing the insertion point are both measured.

Pythonentry point: min_trim_gap

def min_trim_gap(blocks):
    from bisect import bisect_left
    total = sum(blocks)
    half = len(blocks) // 2
    left, right = blocks[:half], blocks[half:]

    def by_count(part):
        size = len(part)
        sums = [0] * (1 << size)
        groups = [[] for _ in range(size + 1)]
        groups[0].append(0)
        for mask in range(1, 1 << size):
            low = mask & -mask
            sums[mask] = sums[mask ^ low] + part[low.bit_length() - 1]
            groups[bin(mask).count("1")].append(sums[mask])
        return groups

    lgroups = by_count(left)
    rgroups = by_count(right)
    for group in rgroups:
        group.sort()

    best = None
    for taken in range(half + 1):
        others = rgroups[half - taken]
        for near in lgroups[taken]:
            rest = total - 2 * near
            pos = bisect_left(others, rest / 2)
            for j in (pos - 1, pos):
                if 0 <= j < len(others):
                    gap = abs(rest - 2 * others[j])
                    if best is None or gap < best:
                        best = gap
    return best

The obvious version

Walk every bit mask over all 2n blocks, keep the masks that select exactly n of them, add up the selected trims directly and track the smallest gap. O(2^(2n) * n).

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_min_trim_gap(blocks):
    count = len(blocks)
    half = count // 2
    whole = sum(blocks)
    best = None
    for mask in range(1 << count):
        if bin(mask).count("1") != half:
            continue
        near = 0
        for i in range(count):
            if mask >> i & 1:
                near += blocks[i]
        gap = abs(whole - 2 * near)
        if best is None or gap < best:
            best = gap
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 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