3Sum Closest - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
Although 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.
Code
Python
Complexity
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.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
C
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 | — |
Detailed 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 |
Video Solution
LeetCode 3Sum Closest Explained - Java • Nick White • 54,561 views views
Watch 9 more video solutions →Frequently Asked Questions
Is 3Sum Closest easy or hard?
How to solve 3Sum Closest in O(n)?
What is the best approach for 3Sum Closest?
3Sum Closest Python or Java solution pattern
What data structure is used in 3Sum Closest?
What is the time complexity of 3Sum Closest?
Is 3Sum Closest asked at Google, Amazon, or Meta interviews?
Ready to solve this problem?
Practice 3Sum Closest with our built-in code editor and test cases.
Practice on FleetCode