Watch 10 video solutions for 3Sum Closest, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by Nick White has 54,353 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. 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 | 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 |