16. 3Sum Closest - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
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.

Examples:

Example 1:
- Input: nums = [-1, 2, 1, -4], target = 1
- Output: 2
- Explanation:
  The sum that is closest to 1 is 2. (i.e., -1 + 2 + 1 = 2)
Example 2:
- Input: nums = [0, 0, 0], target = 1
- Output: 0
- Explanation:
  The only possible sum is 0, which is the closest to target 1.

Constraints:

$(3 \leq \text{nums.length} \leq 500)$
$(-10^3 \leq \text{nums}[i] \leq 10^3)$
$(-10^4 \leq \text{target} \leq 10^4)$

Hints Before the Solution

Sorting is Key:
Sorting the array can simplify the process of finding three numbers. Once sorted, you can use the two-pointer technique to efficiently explore possible triplets.
Two-Pointer Technique:
After fixing one number, use two pointers (one starting just after the fixed number and the other at the end) to find the pair that, together with the fixed number, yields a sum closest to the target.
Tracking the Closest Sum:
Maintain a variable to store the sum of the triplet that is closest to the target. Update this value whenever you find a sum that is closer than the current best.

Approaches

Approach 1: Sorting and Two-Pointer Technique (Optimal)

Idea:

Sort the Array:
Begin by sorting the array in ascending order.
Iterate and Fix One Element:
Loop through the array using an index i to fix one element at a time.
Two-Pointer Search for the Remaining Pair:
For each fixed element nums[i], set two pointers:
- left = i + 1
- right = n - 1
  Then, compute the sum of the triplet:
  $[ \text{sum} = \text{nums}[i] + \text{nums}[left] + \text{nums}[right] ]$
Compare this sum to the target:
- If the sum equals the target, you’ve found the exact answer.
- If the sum is less than the target, move the left pointer rightward to increase the sum.
- If the sum is greater than the target, move the right pointer leftward to decrease the sum.
Update the Closest Sum:
Maintain a variable (say, closestSum) that gets updated whenever a triplet with a sum closer to the target is found.

Time Complexity:

Sorting takes O(n log n).
The two-pointer iteration inside a loop is O(n²).
Overall complexity is O(n²).

Space Complexity:

O(1) extra space (apart from the input array), if we sort the array in-place.

Code Implementations

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Time Complexity:
Sorting takes O(n log n) and the two-pointer approach inside the loop takes O(n²). Overall, the time complexity is O(n²).
Space Complexity:
The solution uses O(1) extra space if sorting is done in-place.

Step-by-Step Walkthrough with Visual Example

Consider nums = [-1, 2, 1, -4] and target = 1:

Sorting the Array:
Sorted array becomes: [-4, -1, 1, 2].
Iteration:
- Iteration with i = 0:
  - Fixed element: -4
  - Initialize left = 1 and right = 3.
  - Calculate currSum = -4 + (-1) + 2 = -3.
    - Difference: | -3 - 1 | = 4.
    - Update closestSum to -3.
    - Since currSum (-3) < target (1), move left pointer right to index 2.
  - Now, left = 2, right = 3.
  - Calculate currSum = -4 + 1 + 2 = -1.
    - Difference: | -1 - 1 | = 2.
    - Update closestSum to -1.
    - Since currSum (-1) < target (1), move left pointer right to index 3.
  - Now left equals right; end inner loop.
- Iteration with i = 1:
  - Fixed element: -1
  - Initialize left = 2 and right = 3.
  - Calculate currSum = -1 + 1 + 2 = 2.
    - Difference: | 2 - 1 | = 1.
    - Update closestSum to 2 (since 1 is closer than 2 away from target compared to previous difference 2).
    - Since currSum (2) > target (1), move right pointer left to index 2.
  - Now left equals right; end inner loop.
Final Result:
After iterating through possible triplets, the closest sum found is 2.

Common Mistakes

Not Sorting the Array:
Forgetting to sort the array can make it difficult to apply the two-pointer technique correctly.
Incorrect Pointer Movement:
Not moving the left pointer when the current sum is less than the target or the right pointer when the current sum is greater than the target can lead to missing the optimal solution.
Initialization of Closest Sum:
Ensure the closest sum is initialized in a way that it can be updated correctly (using a very large initial value or initializing it with the sum of the first triplet).

Edge Cases

Array with Exactly Three Elements:
The answer will simply be the sum of those three elements.
Duplicates in the Array:
Duplicates do not affect the logic as long as the pointers are moved appropriately.
Target Sum Is Far Away:
When the target is much larger or smaller than any possible triplet sum, the algorithm still finds the closest sum.

Alternative Variation:
Variants might ask for the triplet itself rather than the sum, or for all triplets that are closest to the target. Adjustments to the two-pointer logic would be needed.
Related Problems for Further Practice:
- 3Sum (find all triplets that sum to zero)
- 4Sum (find quadruplets that sum to a target)
- Two Sum (find two numbers that add up to a target)