Show problems as
Classic problem #16MediumArrayTwo PointersSorting

3Sum Closest

Real-world version: Three-Weight Ballast Trim
Tracked in this browser only
Read 3Sum Closest on LeetCode(opens in a new tab)

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

Learn the pattern firstTwo Pointers · Arrays, animated step by step

A submersible carries a rack of ballast pods. Releasing a pod shifts the craft's trim by a signed amount, listed in pods: a positive amount lifts the nose, a negative amount drops it.

The pilot has to release exactly three pods, taken from three different rack positions, and wants the shifts to add up as near as possible to goal.

Return that combined shift, not the positions. Two different choices can land the same distance away on opposite sides of goal; when that happens, return the smaller of the two totals.

Examples

Example 1

Input
pods = [-4, 3, 9, 12], goal = 7
Output
8

Releasing the pods worth -4, 3 and 9 shifts trim by 8, one short of the goal. The other three choices land at 11, 17 and 24, all further off.

Example 2

Input
pods = [-7, -4, -3, 6, 9], goal = 5
Output
2

Two choices sit three away: -4, -3 and 9 total 2, while -7, 6 and 9 total 8. Nothing lands nearer, so the tie rule hands back the smaller total.

Example 3

Input
pods = [-1000, -1000, -1000, 1000], goal = -10000
Output
-3000

The rack cannot drop the nose anywhere near that far, so the lowest reachable total, -3000, is the closest it can get.

Constraints

  • 3 <= pods.length <= 500
  • -1000 <= pods[i] <= 1000
  • -10^4 <= goal <= 10^4
  • The three pods must come from three distinct rack positions; equal amounts at different positions are different choices
  • If two reachable totals are equally far from goal, the smaller total is the answer

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 closest_trim_total(pods: list[int], goal: int) -> int:
Java
public int closestTrimTotal(int[] pods, int goal)

More on the same topics