Watch 10 video solutions for 3Sum Closest, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 980,205 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104Problem 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. Unlike the classic 3Sum problem, you don't need an exact match—you track the combination with the smallest absolute difference from the target.
Approach 1: Two-Pointer Approach (Sorting + Two Pointers) (Time: O(n^2), Space: O(1))
Start by sorting the array using sorting. Then iterate through the array and treat each element as the first number of the triplet. For the remaining part of the array, place two pointers: one at the next index (left) and one at the end (right). Compute the current sum nums[i] + nums[left] + nums[right] and compare it with the target. If the sum is closer than the previously recorded value, update the best result.
If the current sum is smaller than the target, move the left pointer forward to increase the sum. If the sum is larger, move the right pointer backward to reduce it. This pointer movement works because the array is sorted. The outer loop runs n times and the inner two-pointer scan runs O(n), giving O(n^2) time complexity with constant extra space.
This method relies heavily on the two pointers pattern and sequential traversal of an array. It avoids checking all triplets explicitly and prunes the search space by adjusting pointers based on the current sum.
Approach 2: Hashmap Based Approach (Time: O(n^2), Space: O(n))
This approach fixes two numbers and uses a hashmap to track the third candidate. For each pair (i, j), compute the remaining value needed to reach the target and check the map for numbers seen so far. While scanning, calculate the sum of the triplet and update the closest result when the difference improves.
The hashmap stores previously visited numbers and allows constant-time lookup for complements. However, because every pair must still be evaluated, the overall complexity remains O(n^2). The additional storage for the map increases the space complexity to O(n). In practice, this approach is less common for this problem since pointer movement on a sorted array is simpler and more cache-friendly.
Recommended for interviews: Interviewers expect the sorting + two-pointer solution. A brute-force triple loop (O(n^3)) shows you understand the problem but does not scale. The optimized two-pointer method demonstrates knowledge of array sorting and pointer techniques, reducing the search space efficiently while maintaining O(n^2) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Three Nested Loops) | O(n^3) | O(1) | Conceptual baseline or very small arrays |
| Two-Pointer After Sorting | O(n^2) | O(1) | Standard interview solution; efficient for general cases |
| Hashmap Based Approach | O(n^2) | O(n) | Useful when experimenting with complement lookups or hash-based patterns |