3Sum Closest solution and explanation
Google
TCS
9 more videos on this problem
LeetCode 3Sum Closest Explained - JavaNick White · 6:25 · 54K views
Three Sum Closest (LeetCode 16) | Full Solution with visual explanation | Interview EssentialNikhil Lohia · 12:25 · 44K views
3 Sum Closest || Leetcode Daily Challenge || Code + Intuition + ExampleCode with Alisha · 13:36 · 38K views
3Sum Closest - (Meta, Amazon, Microsoft, Oracle)➕Live Coding 🧑🏻💻codestorywithMIK · 14:31 · 29K views
3Sum Closest - Leetcode 16 - Two Pointers (Python)Greg Hogg · 8:54 · 15K views
Python Programming Practice: LeetCode #16 -- 3Sum ClosestDataDaft · 16:03 · 8K views
3Sum Closest - LeetCode 16 - Coding Interview QuestionsOne Code Man · 6:26 · 6K views
3Sum Closest | LeetCode 16 | Theory + PythonSai Anish Malla · 8:22 · 4K views
LeetCode Tutorial 16. 3Sum ClosestGoodTecher · 18:15 · 3K views
16. 3Sum Closest | Leetcode | Medium | Java | 2 Pointers | Google Interview QuestionAlgorithmHQ · 4:35 · 2K views
The problem
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.
Example 1:
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).
Example 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).
Constraints:
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-104 <= target <= 104
Approach overview
Problem Overview: Given an integer array nums and a target value, find three numbers whose sum is closest to the target. Return the sum of those three numbers. The goal is not to find an exact match but the combination with the smallest absolute difference from the target.
Approach 1: Hashmap Based Search (O(n^2) time, O(n) space)
This approach fixes one element and reduces the problem to a variation of the two‑sum closest problem. For each index i, iterate through the remaining elements while storing previously seen numbers in a hash set or hashmap. For the current value nums[j], compute the complement needed to reach the target relative to nums[i]. Instead of requiring an exact match, track the closest sum seen so far by comparing |target - currentSum|. Hash lookups run in constant time, so each outer iteration scans the rest of the array with O(1) membership checks. This approach works without sorting and is useful when you want a straightforward extension of hash-based two‑sum logic, but it still runs in O(n^2) time and requires O(n) extra memory.
Approach 2: Sorting + Two Pointers (O(n^2) time, O(1) space)
The most common solution starts by sorting the array. After sorting, fix one element at index i and use two pointers to search the remaining portion of the array. Initialize left = i + 1 and right = n - 1. Compute the sum of nums[i] + nums[left] + nums[right]. If the sum is closer to the target than the previous best, update the result. If the sum is less than the target, move the left pointer forward to increase the sum; if it is greater, move the right pointer backward to decrease it. Because the array is sorted, pointer movement systematically explores all candidate triplets without redundant checks. The outer loop runs n times and the two‑pointer scan runs in linear time, giving O(n^2) time complexity with O(1) extra space.
This pattern appears frequently in problems built on array manipulation after sorting. The two-pointer technique efficiently narrows the search range by moving inward from both ends, a common strategy in two pointers problems.
Recommended for interviews: The sorting + two‑pointer approach is what interviewers usually expect. It demonstrates that you recognize the relationship to the classic 3Sum pattern and can optimize the search space after sorting. A hash-based variant can still show good problem decomposition, but the two‑pointer solution is cleaner, uses constant extra space, and communicates stronger algorithmic intuition.
Approach 1: Two-pointer Approach
This approach involves first sorting the array, and then using a two-pointer technique. For each element, we treat it as the first element of a potential triplet and place two pointers at the ends of the remaining subarray. We then move these pointers inward, calculating the sum at each position and comparing it to the target. By maintaining the sum closest to the target found so far, we can track the desired result.
def threeSumClosest(nums, target):
nums.sort()
closest_sum = float('inf')
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if abs(target - current_sum) < abs(target - closest_sum):
closest_sum = current_sum
if current_sum < target:
left += 1
elif current_sum > target:
right -= 1
else:
return current_sum
return closest_sumimport java.util.Arrays;
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closestSum = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1, right = nums.length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
closestSum = currentSum;
}
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum;
}
}
}
return closestSum;
}
}#include <vector>
#include <algorithm>
#include <cmath>
class Solution {
public:
int threeSumClosest(std::vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end());
int closestSum = INT_MAX / 2; // Use a number that won't cause overflow
for (int i = 0; i < nums.size() - 2; i++) {
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (std::abs(target - currentSum) < std::abs(target - closestSum)) {
closestSum = currentSum;
}
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum;
}
}
}
return closestSum;
}
};var threeSumClosest = function(nums, target) {
nums.sort((a, b) => a - b);
let closestSum = Infinity;
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1,
right = nums.length - 1;
while (left < right) {
const currentSum = nums[i] + nums[left] + nums[right];
if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
closestSum = currentSum;
}
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum;
}
}
}
return closestSum;
};#include <stdlib.h>
#include <limits.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void quicksort(int* nums, int low, int high) {
if (low < high) {
int pi = partition(nums, low, high);
quicksort(nums, low, pi - 1);
quicksort(nums, pi + 1, high);
}
}
int partition(int* nums, int low, int high) {
int pivot = nums[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (nums[j] < pivot) {
i++;
swap(&nums[i], &nums[j]);
}
}
swap(&nums[i + 1], &nums[high]);
return (i + 1);
}
int threeSumClosest(int* nums, int numsSize, int target) {
quicksort(nums, 0, numsSize - 1);
int closestSum = INT_MAX / 2;
for (int i = 0; i < numsSize - 2; i++) {
int left = i + 1, right = numsSize - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (abs(target - currentSum) < abs(target - closestSum)) {
closestSum = currentSum;
}
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum;
}
}
}
return closestSum;
}using System;
public class Solution {
public int ThreeSumClosest(int[] nums, int target) {
Array.Sort(nums);
int closestSum = int.MaxValue / 2;
for (int i = 0; i < nums.Length - 2; i++) {
int left = i + 1, right = nums.Length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum)) {
closestSum = currentSum;
}
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum;
}
}
}
return closestSum;
}
}We begin by sorting the array to simplify the evaluation of possible sums using a two-pointer technique.
We iterate over the array with a fixed element and set two pointers: one initial (left) and the other one at the end of the array (right). We attempt to bring their sum closer to the target by moving these pointers inward based on the evaluation.
Throughout, we track the closest sum to the target found so far and update it whenever we find a sum with a smaller absolute difference from the target.
Time Complexity: O(n^2) as the sorting takes O(n log n) and the two-pointer scanning for each element takes O(n).
Space Complexity: O(1) as no additional space is used apart from input handling.
Approach 2: Hashmap based Approach
An alternative approach uses a hashmap to store results of sums previously obtained, attempting to minimize recalculation. This helps when you want quick hash-map based lookups. Although less commonly optimal for this problem, its concept is crucial to explore for diverse method understanding. However, the typical 3Sum problem resolved via hashmap cannot be translated well into this one because storing potential sums doesn't help reduce the complexity below O(n^2) as comparisons per pair are required.
# Hashmap approach is commonly less efficient here but holds educational value.
def threeSumClosest(nums, target):
nums.sort()
closest = float('inf')
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
sum_value = nums[i] + nums[left] + nums[right]
if abs(sum_value - target) < abs(closest - target):
closest = sum_value
if sum_value < target:
left += 1
elif sum_value > target:
right -= 1
else:
return closest
return closestAlthough attempting to use a hashmap for distinct sums can be slower, the number of cases where recalculation avoided helps understand alternative paradigms for lookup or reference use as applied to sum and distance analysis. Since pairing three amounts prevalently defects hashmap efficiency virtue, this becomes an academic exercise given the nature of two-pointer solutions being inherently simpler.
Time Complexity: Still O(n^2) due to needed dual-pointer validation.
Space Complexity: Could exceed simplicity due to extra dictionary operations, no pragmatic benefit here.
Approach 3: Sorting + Two Pointers
We sort the array first, then traverse the array. For each element nums[i], we use pointers j and k to point to i+1 and n-1 respectively, calculate the sum of the three numbers. If the sum of the three numbers equals target, we directly return target. Otherwise, we update the answer based on the difference from target. If the sum of the three numbers is greater than target, we move k one place to the left, otherwise, we move j one place to the right.
The time complexity is O(n^2), and the space complexity is O(log n). Here, n is the length of the array.
function threeSumClosest(nums: number[], target: number): number {
nums.sort((a, b) => a - b);
let ans: number = 1 << 30;
const n = nums.length;
for (let i = 0; i < n; ++i) {
let j = i + 1;
let k = n - 1;
while (j < k) {
const t: number = nums[i] + nums[j] + nums[k];
if (t === target) {
return t;
}
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
}
if (t > target) {
--k;
} else {
++j;
}
}
}
return ans;
}func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
ans := 1 << 30
n := len(nums)
for i, v := range nums {
j, k := i+1, n-1
for j < k {
t := v + nums[j] + nums[k]
if t == target {
return t
}
if abs(t-target) < abs(ans-target) {
ans = t
}
if t > target {
k--
} else {
j++
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}class Solution {
/**
* @param int[] $nums
* @param int $target
* @return int
*/
function threeSumClosest($nums, $target) {
$n = count($nums);
$closestSum = $nums[0] + $nums[1] + $nums[2];
$minDiff = abs($closestSum - $target);
sort($nums);
for ($i = 0; $i < $n - 2; $i++) {
$left = $i + 1;
$right = $n - 1;
while ($left < $right) {
$sum = $nums[$i] + $nums[$left] + $nums[$right];
$diff = abs($sum - $target);
if ($diff < $minDiff) {
$minDiff = $diff;
$closestSum = $sum;
} elseif ($sum < $target) {
$left++;
} elseif ($sum > $target) {
$right--;
} else {
return $sum;
}
}
}
return $closestSum;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-pointer Approach | Time Complexity: O(n^2) as the sorting takes O(n log n) and the two-pointer scanning for each element takes O(n). Space Complexity: O(1) as no additional space is used apart from input handling. |
| Hashmap based Approach | Time Complexity: Still O(n^2) due to needed dual-pointer validation. Space Complexity: Could exceed simplicity due to extra dictionary operations, no pragmatic benefit here. |
| Sorting + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashmap Based Search | O(n^2) | O(n) | When adapting two-sum style hash lookups without sorting the array |
| Sorting + Two Pointers | O(n^2) | O(1) | Best general solution after sorting; optimal space and standard interview approach |
Frequently asked questions
Is 3Sum Closest easy or hard?
3Sum Closest is typically classified as a medium difficulty problem. The logic becomes straightforward once you recognize the connection to the classic 3Sum problem and apply sorting with a two-pointer scan.
How to solve 3Sum Closest in O(n)?
Solving 3Sum Closest in strict O(n) time is not possible for the general case because every element can potentially form combinations with two others. The best known practical approach is O(n^2) using sorting and the two-pointer technique.
What is the best approach for 3Sum Closest?
The best approach is sorting the array followed by a two-pointer scan. After fixing one element, move two pointers from both ends of the remaining array to adjust the sum toward the target. This runs in O(n^2) time and O(1) extra space and is the solution most interviewers expect.
3Sum Closest Python or Java solution pattern
Most Python and Java implementations follow the same pattern: sort the array, iterate with index i, and apply two pointers left and right to compute candidate sums. Update the closest sum whenever a smaller difference from the target is found. The algorithm runs in O(n^2) time.
What data structure is used in 3Sum Closest?
The primary structures involved are arrays and pointer indices. The optimal approach relies on sorting the array and then using two pointers to scan inward. Some alternative implementations use a hashmap or hash set to store complements during iteration.
What is the time complexity of 3Sum Closest?
The optimal solution runs in O(n^2) time. Sorting takes O(n log n), and for each element you perform a linear two-pointer scan across the rest of the array. The space complexity is O(1) beyond the input array.
Is 3Sum Closest asked at Google, Amazon, or Meta interviews?
3Sum Closest appears in interviews at companies such as Amazon, Meta, and Google because it tests array manipulation, sorting, and two-pointer reasoning. Interviewers often use it to evaluate whether candidates can adapt the classic 3Sum pattern to a slightly different objective.