Approximate Three Sum

The Problem

Given an integer array arr and an integer target, find the sum of three integers in the array that is closest to target. Return that sum. It is guaranteed that exactly one answer exists.

Input:  arr = [-1, 2, 1, -4],  target = 1
Output: 2
Explanation: -1 + 2 + 1 = 2 is the closest sum to 1. (-1 + 2 + (-4) = -3 is further away)

Examples

Example 1

Input:  arr = [-1, 2, 1, -4],  target = 1
Output: 2
Explanation: (-1) + 2 + 1 = 2. |2 - 1| = 1 (distance from target).

Example 2

Input:  arr = [0, 0, 0],  target = 1
Output: 0
Explanation: Only triplet is 0+0+0=0. |0-1|=1.

Example 3

Input:  arr = [1, 1, 1, 0],  target = -100
Output: 2
Explanation: Closest to -100 is still 0+1+1=2, as all sums are positive.

Intuition

This is Three Sum with a modified goal: instead of finding a triplet that equals zero, find the triplet whose sum is closest to a given target. The structure is identical:

1. Sort the array
2. Fix one element arr[i]
3. Two-pointer on the rest, but instead of checking equality, track the minimum distance |sum - target|
4. Move pointers based on whether the current sum is above or below target

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr"]
  Init["closest = arr[0]+arr[1]+arr[2]"]
  Outer["for i in 0 → n-3"]
  SetTP["left = i+1,  right = n-1"]
  InLoop{"left < right?"}
  Calc["total = arr[i] + arr[left] + arr[right]"]
  Update["|total-target| < |closest-target|?\n→ closest = total"]
  ExactMatch{"total == target?"}
  RetEarly(["return target"])
  TooSmall{"total < target?"}
  MoveL["left++  (need larger sum)"]
  MoveR["right--  (need smaller sum)"]
  Done(["return closest"])

  Sort --> Init --> Outer --> SetTP --> InLoop
  InLoop -->|"yes"| Calc --> Update --> ExactMatch
  ExactMatch -->|"yes"| RetEarly
  ExactMatch -->|"no"| TooSmall
  TooSmall -->|"yes"| MoveL --> InLoop
  TooSmall -->|"no"| MoveR --> InLoop
  InLoop -->|"no"| Outer
  Outer -->|"done"| Done

Approximate Three Sum — fix one element, two-pointer the rest while tracking the closest sum seen so far.

Solution

from typing import List

class Solution:
    def three_sum_closest(self, arr: List[int], target: int) -> int:
        # Sort the array to enable the two-pointer subproblem approach
        arr.sort()
        n = len(arr)
        # Initialize closest with the first valid triplet as the starting baseline
        closest = arr[0] + arr[1] + arr[2]

        for i in range(n - 2):
            # Set up the two-pointer subproblem on the subarray after arr[i]
            left, right = i + 1, n - 1

            while left < right:
                total = arr[i] + arr[left] + arr[right]

                # Update closest if the current triplet is nearer to target
                if abs(total - target) < abs(closest - target):
                    closest = total

                # Exact match — no closer sum is possible
                if total == target:
                    return target

                if total < target:
                    # Sum too small — move left pointer to a larger value
                    left += 1
                else:
                    # Sum too large — move right pointer to a smaller value
                    right -= 1

        return closest


# --- Test ---
sol = Solution()
print(sol.three_sum_closest([-1, 2, 1, -4], 1))    # 2
print(sol.three_sum_closest([0, 0, 0], 1))          # 0
print(sol.three_sum_closest([1, 1, 1, 0], -100))    # 2
print(sol.three_sum_closest([4, 0, 5, -5, 3, 3, 0, -4, -5], -2))  # -2

Dry Run — Example 1

arr = [-1, 2, 1, -4] → sorted: [-4, -1, 1, 2], target = 1

Initial closest = -4 + (-1) + 1 = -4

i=0, arr[i]=-4:

| left | right | total | |total-1| | |closest-1| | Update? | Action | |—|—|—|—|—|—|—| | 1 (-1) | 3 (2) | -4+(-1)+2 = -3 | 4 | 5 | ✅ closest=-3 | -3<1 → left++ | | 2 (1) | 3 (2) | -4+1+2 = -1 | 2 | 4 | ✅ closest=-1 | -1<1 → left++ | | 3=right | — | — | — | — | — | stop |

i=1, arr[i]=-1:

| left | right | total | |total-1| | |closest-1| | Update? | Action | |—|—|—|—|—|—|—| | 2 (1) | 3 (2) | -1+1+2 = 2 | 1 | 2 | ✅ closest=2 | 2>1 → right– | | 2 | 2 | — | — | — | — | stop |

i=2: only one element left (n-2=2), loop ends.

Return 2 ✓ (|2-1| = 1, best achievable)

Complexity Analysis

Comparison With Three Sum

The structural difference is minimal — swap “record match” for “update closest” and remove the duplicate-skipping logic.

Edge Cases

Key Takeaway

Approximate Three Sum demonstrates that the two-pointer subproblem pattern is goal-agnostic: the pointer movement logic (sum too small → left++, sum too large → right–) is driven purely by whether we need to increase or decrease the running total. Swapping the target from “exactly 0” to “closest to target” requires only changing how we evaluate results, not how we move pointers.