How do you solve 3Sum Closest?

Sort the array. For each element, use two pointers starting just after the fixed element and at the end of the array. Calculate the sum of the three elements. If the sum equals the target, return immediately. Otherwise, update the closest sum if the current sum is nearer to the target. Move the left pointer right if the sum is less than the target, or the right pointer left if the sum is greater. Continue until pointers meet. Return the closest sum found.

3Sum Closest

Q: What is the time complexity of 3Sum Closest?

O(n^2). Sorting takes O(n log n). The main loop runs O(n) times, and for each iteration, the two-pointer scan runs in O(n), resulting in O(n^2) overall.

Q: What pattern does 3Sum Closest use?

The Pattern: Two Pointers (Sorted Array Pair Search) The Heuristic: When searching for pairs or triplets with a sum condition in a sorted array, fix one element and use two pointers moving inward to efficiently find the best complement, eliminating the need for nested loops and reducing complexity from O(n^3) to O(n^2).

Medium Two Pointers

Problem

Given an integer array nums and an integer target, return the sum of three integers in nums such that the sum is closest to target. You may assume that each input would have exactly one solution.

3 ≤ nums.length ≤ 10³
−10³ ≤ nums[i] ≤ 10³
−10⁴ ≤ target ≤ 10⁴

Example

Input: nums = [-1, 2, 1, -4], target = 1

Output: 2

Sorting the array results in [-4, -1, 1, 2]. Starting with the first element -4, the two-pointer approach checks pairs (left=1, right=2) to find sums closest to 1. The sum (-4 + 1 + 2 = -1) is 2 away from target. Moving pointers and iterating through the array, the closest sum found is 2 (-1 + 1 + 2), which is only 1 away from target. The algorithm returns 2 as the closest sum.

Approach

Straightforward Solution

A brute-force approach would check all triplets (O(n^3)) and track the closest sum, which is inefficient for large inputs.

Core Observation

The problem requires finding three numbers whose sum is closest to a target. Sorting the array enables a two-pointer approach to efficiently explore pairs for each fixed element, reducing the search space from O(n^3) to O(n^2).

Path to Optimal

Preview

Sorting the array allows fixing one element and using two pointers to scan the remaining elements for the best pair complement. This reduces complexity to O(n^2)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the array. For each element, use two pointers starting just after the fixed element and at the end of the array…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

Sorting takes O(n log n). The main loop runs O(n) times, and for each iteration, the two-pointer scan runs in O(n), resulting in O(n^2) overall.

Space

O(1)

The algorithm sorts the input in place and uses only a fixed number of variables, requiring constant auxiliary space.

Pattern Spotlight

Two Pointers (Sorted Array Pair Search)

When searching for pairs or triplets with a sum condition in a sorted array, fix one element and use two pointers moving inward to efficiently find the best complement, eliminating the need for nested loops and reducing complexity from O(n^3) to O(n^2).

Solution

Python

1class Solution:
  def threeSumClosest(self, nums: list[int], target: int) -> int:
      nums.sort()
4
      closest = nums[0] + nums[1] + nums[2]
6
      for i in range(len(nums) - 2):
          left = i + 1
          right = len(nums) - 1
10
          while left < right:
              total = nums[i] + nums[left] + nums[right]
13
              if abs(total - target) < abs(closest - target):
                  closest = total
16
              if total < target:
                  left += 1
              elif total > target:
                  right -= 1
              else:
                  return target
23
      return closest

Step-by-Step Solution

Sort the Array and Initialize Closest Sum

3nums.sort()
5closest = nums[0] + nums[1] + nums[2]

Objective

To prepare the input for efficient two-pointer scanning by sorting and to initialize the closest sum with the first triplet.

Key Insight

Sorting the array is essential to apply the two-pointer technique. Initializing the closest sum with the first three elements provides a baseline for comparison, ensuring the algorithm always has a valid candidate to update.

Interview Quick-Check

Core Logic

Sorting enables the two-pointer approach by ordering elements, which allows pointer movements to predictably increase or decrease the sum.

State & Boundaries

Initializing closest with the sum of the first three elements ensures a valid starting point for comparison.

Common Pitfalls & Bugs

Failing to sort the array breaks the two-pointer logic, as pointer movements would not reliably adjust the sum towards the target.

Iterate Through Array Fixing One Element and Use Two Pointers to Find Closest Sum

To explore all triplets by fixing one element and using two pointers to find the pair that yields the sum closest to the target.

Return the Closest Sum Found

To output the sum of three integers closest to the target after exploring all valid triplets.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 21 Critical

else:

If the current sum equals the target, return the target immediately.

An exact match is the closest possible sum, so the algorithm can terminate early for optimal efficiency.

Line 22 Critical

return target

Return the target immediately upon exact match.

Immediate return avoids unnecessary computation once the optimal solution is found, improving performance.

Line 3 Critical

nums.sort()

Sort the input array in ascending order.

Sorting is critical because it enables the two-pointer technique by ensuring that moving pointers inward predictably increases or decreases the sum, allowing efficient search.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why does moving the pointer at the smaller or larger value help find a sum closer to the target?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct 3Sum Closest from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the 3Sum Closest drill

or drill a free problem

1	`class Solution:`
2	`def threeSumClosest(self, nums: list[int], target: int) -> int:`
3	`nums.sort()`
4
5	`closest = nums[0] + nums[1] + nums[2]`
6
7	`for i in range(len(nums) - 2):`
8	`left = i + 1`
9	`right = len(nums) - 1`
10
11	`while left < right:`
12	`total = nums[i] + nums[left] + nums[right]`
13
14	`if abs(total - target) < abs(closest - target):`
15	`closest = total`
16
17	`if total < target:`
18	`left += 1`
19	`elif total > target:`
20	`right -= 1`
21	`else:`
22	`return target`
23
24	`return closest`