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.
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.
Java
C++
C
C#
JavaScript
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.
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.
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 | 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. |
| 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 |
3Sum - Leetcode 15 - Python • NeetCode • 980,205 views views
Watch 9 more video solutions →Practice 3Sum Closest with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor