3Sum Closest – Solution & Complexity

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

The optimal 3Sum Closest solution runs in `O(n^2)` time and `O(1) extra` space. Sort the array, fix one value, then two-pointer scan the rest while tracking the closest triplet sum.

Q: What is the most efficient way to solve 3Sum Closest?

Sort the array, fix one value, then two-pointer scan the rest while tracking the closest triplet sum. This gives `O(n^2)` time complexity, and is a classic arrays, two pointers, and sorting problem.

Q: How do you solve 3Sum Closest in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked 3Sum Closest solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is 3Sum Closest an easy or hard interview question?

3Sum Closest is generally rated **Medium**. It tests arrays, two pointers, and sorting, which are common coding-interview patterns.

Solution Walkthrough

Step 1: Start with the brute-force search space
- Any valid answer comes from choosing three different indices.
- The most direct solution is to try every triplet, compute its sum, and keep the one with the smallest absolute distance from target.
- This is easy to reason about and makes a good correctness baseline, but it checks O(n^3) triplets.

Step 2: Brute-force triple loop

Initialize best_sum using the first three values.
Enumerate every i < j < k combination, compute the current sum, and update best_sum whenever the new sum is closer to target.
Because the problem guarantees exactly one closest sum, a strict < comparison is enough when updating the best answer.

def three_sum_closest(nums: list[int], target: int) -> int:
    best_sum = nums[0] + nums[1] + nums[2]

    for i in range(len(nums) - 2):
        for j in range(i + 1, len(nums) - 1):
            for k in range(j + 1, len(nums)):
                current = nums[i] + nums[j] + nums[k]
                if abs(current - target) < abs(best_sum - target):
                    best_sum = current

    return best_sum

Step 3: Sort first, then scan with two pointers
- After sorting, fix one value nums[i] and search for the best pair in the suffix i + 1 .. n - 1.
- With a sorted array, if the current triplet sum is too small, moving left right is the only way to increase it; if the sum is too large, moving right left decreases it.
- This turns the inner O(n^2) pair search into a linear two-pointer walk for each fixed i, reducing the total to O(n^2) after sorting.

Step 4: Final optimal solution

Sort the array, initialize the best answer from the first triplet, then for each index run a two-pointer scan to keep improving the closest sum. Sorting costs O(n log n), the scans cost O(n^2), and the total is O(n^2) with O(1) extra space beyond the sort.

def three_sum_closest(nums: list[int], target: int) -> int:
    nums = sorted(nums)
    best_sum = nums[0] + nums[1] + nums[2]

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:
            current = nums[i] + nums[left] + nums[right]
            if abs(current - target) < abs(best_sum - target):
                best_sum = current

            if current < target:
                left += 1
            elif current > target:
                right -= 1
            else:
                return current

    return best_sum

3Sum Closest – Solution & Complexity

Solution Walkthrough

Step 1: Start with the brute-force search space

Step 2: Brute-force triple loop

Step 3: Sort first, then scan with two pointers

Step 4: Final optimal solution

FAQ

What is the time and space complexity of 3Sum Closest?

What is the most efficient way to solve 3Sum Closest?

How do you solve 3Sum Closest in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is 3Sum Closest an easy or hard interview question?

See also

3Sum Closest – Solution & Complexity

Solution Walkthrough

1Step 1: Start with the brute-force search space

2Step 2: Brute-force triple loop

3Step 3: Sort first, then scan with two pointers

4Step 4: Final optimal solution

FAQ

What is the time and space complexity of 3Sum Closest?

What is the most efficient way to solve 3Sum Closest?

How do you solve 3Sum Closest in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is 3Sum Closest an easy or hard interview question?

See also

Step 1: Start with the brute-force search space

Step 2: Brute-force triple loop

Step 3: Sort first, then scan with two pointers

Step 4: Final optimal solution