title: 3Sum Closest
slug: three-sum-closest
difficulty: medium
leetcode_id: 16
leetcode_url: https://leetcode.com/problems/3sum-closest/
categories:
  - arrays
  - two-pointers
  - sorting
patterns:
  - slug: two-pointers
    is_optimal: true

function_signature: "def three_sum_closest(nums: list[int], target: int) -> int:"

test_cases:
  visible:
    - input: { nums: [-1, 2, 1, -4], target: 1 }
      expected: 2
    - input: { nums: [0, 0, 0], target: 1 }
      expected: 0
  hidden:
    - input: { nums: [1, 1, 1, 0], target: -100 }
      expected: 2
    - input: { nums: [1, 2, 3, 4, 5], target: 10 }
      expected: 10
    - input: { nums: [-1, 0, 1, 1, 55], target: 3 }
      expected: 2
    - input: { nums: [1, 1, -1, -1, 3], target: -1 }
      expected: -1
    - input: { nums: [-100, -50, 0, 50, 100], target: 1 }
      expected: 0
    - input: { nums: [4, 0, 5, -5, 3, 3, 0, -4, -5], target: -2 }
      expected: -2

description: |
  Given an integer array `nums` of length `n` and an integer `target`, find three integers in `nums` such that the sum is **closest** to `target`.

  Return *the sum of the three integers*.

  You may assume that each input would have exactly one solution.

constraints: |
  - `3 <= nums.length <= 500`
  - `-1000 <= nums[i] <= 1000`
  - `-10^4 <= target <= 10^4`

examples:
  - input: "nums = [-1,2,1,-4], target = 1"
    output: "2"
    explanation: "The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)."
  - input: "nums = [0,0,0], target = 1"
    output: "0"
    explanation: "The sum that is closest to the target is 0. (0 + 0 + 0 = 0)."

explanation:
  intuition: |
    This problem is a close cousin of 3Sum, with one key difference: instead of finding triplets that sum to exactly zero, we want the triplet whose sum is **closest** to a target value.

    Think of it like a number line. Imagine plotting all possible triplet sums on this line, with the target marked. Your job is to find which triplet sum lands nearest to the target — whether it lands exactly on it, slightly below, or slightly above.

    The key insight is the same as 3Sum: **sorting unlocks the two-pointer technique**. Once sorted, if our current sum is too small, we can systematically increase it by moving the left pointer right. If too large, we move the right pointer left. At each step, we check: is this sum closer to the target than our best so far?

    Unlike 3Sum (which collects all exact matches), we only care about the single closest sum, so we track a "best" answer and update it whenever we find something closer.

  approach: |
    We solve this using **Sort + Two Pointers**:

    **Step 1: Sort the array**

    - Sorting is essential for the two-pointer technique
    - After sorting, we can adjust our sum by moving pointers left or right

    &nbsp;

    **Step 2: Initialise tracking variable**

    - `closest_sum`: Store the sum of the first three elements as our initial best guess
    - We'll update this whenever we find a sum closer to the target

    &nbsp;

    **Step 3: Fix the first element and use two pointers**

    - For each index `i` from 0 to n-3:
      - Set `left = i + 1`, `right = n - 1`
      - While `left < right`:
        - Calculate `current_sum = nums[i] + nums[left] + nums[right]`
        - If `current_sum == target`: return immediately — we can't get closer than exact
        - If `abs(current_sum - target) < abs(closest_sum - target)`: update `closest_sum`
        - If `current_sum < target`: move `left` right to increase the sum
        - If `current_sum > target`: move `right` left to decrease the sum

    &nbsp;

    **Step 4: Return the closest sum**

    - After checking all triplets, return `closest_sum`

  common_pitfalls:
    - title: Not Handling Early Termination
      description: |
        If you find a sum that **exactly equals** the target, return immediately. The distance is zero — you can't possibly find anything closer.

        Without this optimisation, you'll waste time checking remaining triplets when the answer is already known.
      wrong_approach: "Continuing to search after finding an exact match"
      correct_approach: "if current_sum == target: return target"

    - title: Brute Force Approach
      description: |
        The naive approach checks all possible triplets with three nested loops:
        - Outer loop `i` from 0 to n-3
        - Middle loop `j` from i+1 to n-2
        - Inner loop `k` from j+1 to n-1

        This results in **O(n³) time complexity**. While the constraint `n <= 500` might allow this to pass, it's unnecessarily slow.

        With sorting + two pointers, we reduce to O(n²) — a 500x speedup for the maximum input size.
      wrong_approach: "Three nested loops checking all triplets"
      correct_approach: "Sort + two pointers for O(n²)"

    - title: Incorrect Distance Comparison
      description: |
        When comparing which sum is closer, use **absolute difference**: `abs(current_sum - target)`.

        A common mistake is comparing raw differences without absolute value, which fails when sums can be both above and below the target.
      wrong_approach: "current_sum - target < closest_sum - target"
      correct_approach: "abs(current_sum - target) < abs(closest_sum - target)"

  key_takeaways:
    - "**Two pointers on sorted arrays**: Sorting transforms the search from O(n²) per fixed element to O(n)"
    - "**Track best-so-far for optimisation problems**: Unlike 3Sum (collect all matches), we maintain a single best answer"
    - "**Early termination on exact match**: When distance is zero, no further search is needed"
    - "**3Sum variant pattern**: Many problems (3Sum, 3Sum Closest, 3Sum Smaller) use the same sort + two-pointer framework with small variations"

  time_complexity: "O(n²). Sorting is O(n log n), then for each of n elements, the two-pointer search is O(n). The dominant term is O(n × n) = O(n²)."
  space_complexity: "O(log n) to O(n). Depends on the sorting algorithm used — O(log n) for in-place sorts like heapsort, O(n) for others like mergesort."

solutions:
  - approach_name: Sort + Two Pointers
    is_optimal: true
    code: |
      def three_sum_closest(nums: list[int], target: int) -> int:
          nums.sort()  # Enable two-pointer technique
          n = len(nums)
          # Start with sum of first three elements as initial guess
          closest_sum = nums[0] + nums[1] + nums[2]

          for i in range(n - 2):
              # Two pointers for the remaining array
              left, right = i + 1, n - 1

              while left < right:
                  current_sum = nums[i] + nums[left] + nums[right]

                  # Exact match — can't get closer than this
                  if current_sum == target:
                      return target

                  # Update closest if this sum is nearer to target
                  if abs(current_sum - target) < abs(closest_sum - target):
                      closest_sum = current_sum

                  # Adjust pointers based on comparison with target
                  if current_sum < target:
                      left += 1  # Need larger sum
                  else:
                      right -= 1  # Need smaller sum

          return closest_sum
    explanation: |
      **Time Complexity:** O(n²) — O(n log n) sort + O(n) two-pointer search for each of O(n) elements.

      **Space Complexity:** O(log n) to O(n) — Sorting space only.

      We sort the array, then for each element, use two pointers to explore sums. We track the closest sum seen, updating when we find one nearer to the target. Early termination on exact match provides a minor optimisation.

  - approach_name: Brute Force
    is_optimal: false
    code: |
      def three_sum_closest(nums: list[int], target: int) -> int:
          n = len(nums)
          # Start with sum of first three elements
          closest_sum = nums[0] + nums[1] + nums[2]

          # Check all possible triplets
          for i in range(n - 2):
              for j in range(i + 1, n - 1):
                  for k in range(j + 1, n):
                      current_sum = nums[i] + nums[j] + nums[k]

                      # Update closest if this sum is nearer
                      if abs(current_sum - target) < abs(closest_sum - target):
                          closest_sum = current_sum

                      # Early exit on exact match
                      if closest_sum == target:
                          return target

          return closest_sum
    explanation: |
      **Time Complexity:** O(n³) — Three nested loops checking all triplets.

      **Space Complexity:** O(1) — Only tracking the closest sum.

      This approach checks every possible triplet combination. While correct, the O(n³) complexity makes it significantly slower than the two-pointer approach. For n=500, this means 20 million comparisons vs 250,000 with the optimal approach.
