Skip to main content

Two Pointer

3Sum Closest Solution In C++/Java/Python/JS

Problem 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 the target. Return the sum of the three integers.

You may assume that each input would have exactly one solution.
3Sum Closest-Problem-Description

Examples:

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).

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
  • -10^4 <= target <= 10^4
💡
Try it Yourself First!
The problem is straightforward yet engaging. We need to find three numbers in the array that sum up to the closest value to a given target. The goal is to check different triplets and determine which one gives the sum nearest to the target.

Brute Force Approach

Intuition

The brute force approach is simple and intuitive: we aim to find three numbers in the array whose sum is closest to the target. To achieve this, we use three nested loops. The first loop selects the first number, the second loop picks the second number, and the third loop chooses the third number. By checking all combinations, we ensure no potential triplet is missed.

For each triplet, we calculate the sum of the three numbers and compare it with the target. The goal is to find the triplet whose sum is closest to the target value. This involves calculating the absolute difference between the triplet’s sum and the target for each combination.

To store the closest result, we initialize a variable, say closestSum, with a large value or the sum of the first triplet. During the iteration, if the absolute difference of the current triplet’s sum and the target is smaller than the previously recorded difference, we update closestSum. This ensures that we always have the most accurate result so far.

By iterating through all possible triplets, this approach guarantees that we find the triplet whose sum is closest to the target. The simplicity of this method makes it an excellent starting point, especially for beginners. Although it checks many combinations, its logic is easy to follow and implement.

This method relies entirely on systematically exploring the array and maintaining the closest sum found. It highlights the power of straightforward iteration when solving problems exhaustively. While not the most efficient approach, it lays the foundation for understanding and optimizing the solution further.

Approach

Step 1: Initialize a variable to store the closest sumStart by creating a variable closestSum and initialize it to a very large value or the sum of the first triplet (if available). This variable will store the sum of the triplet that is closest to the target as we iterate through the array.

Step 2: Loop through the array to pick the first numberUse the first loop to pick the first number in the triplet. Let the index of this number be i. Start the loop from the first element and iterate until the third-last element of the array since we need at least two more numbers for a triplet.

Step 3: Loop through the remaining numbers to pick the second numberFor each first number nums[i], use a second loop to pick the second number. Let the index of this number be j. Start this loop from i + 1 and continue until the second-last element of the array since we still need one more number for a triplet.

Step 4: Loop through the remaining numbers to pick the third numberFor each pair of the first two numbers nums[i] and nums[j], use a third loop to pick the third number. Let the index of this number be k. Start this loop from j + 1 and iterate until the last element of the array.

Step 5: Calculate the sum of the triplet and compare with the targetFor each combination of three numbers nums[i], nums[j], and nums[k], calculate their sum. Check the absolute difference between this sum and the target. If this difference is smaller than the difference for closestSum, update closestSum with the current sum.

Step 6: Continue until all combinations are checkedRepeat the above steps for all possible triplets in the array. By the end of all the loops, closestSum will contain the sum of the triplet that is closest to the target.

Step 7: Return the closest sumAfter exiting the loops, return the value stored in closestSum as the result. This is the sum of the triplet that is closest to the given target.

Let us understand this with a video ,

0:00
/1:05

3Sum Closest-Brute-Force-Approach

3Sum Closest Dry run - BruteForce

Input: nums = [-1, 2, 1, -4], target = 1
Step 1 - Outer Loop (i = 0):The outer loop runs with i = 0 to 3, picking the first number nums[i] each time.

  • i = 0 (first element = -1):We pick nums[i] = -1.

Step 2 - Inner Loop (j = 1 to 3):The inner loop runs for j from i + 1 to 3 (i.e., j = 1 to j = 3).

  • j = 1 (second element = 2):We pick nums[j] = 2.

Step 3 - Inner-Inner Loop (k = 2 to 3):Now, we check for a third number nums[k] by looping k from j + 1 to 3.

  • k = 2 (third element = 1):We check nums[i] + nums[j] + nums[k] = -1 + 2 + 1 = 2.Calculate the difference: |2 - 1| = 1.Update closestSum = 2 (as it’s closer to the target).
  • k = 3 (third element = -4):We check nums[i] + nums[j] + nums[k] = -1 + 2 - 4 = -3.Calculate the difference: |-3 - 1| = 4.No update to closestSum.

Step 2 - Inner Loop (j = 2):

  • j = 2 (second element = 1):We pick nums[j] = 1.

Step 3 - Inner-Inner Loop (k = 3):

  • k = 3 (third element = -4):We check nums[i] + nums[j] + nums[k] = -1 + 1 - 4 = -4.Calculate the difference: |-4 - 1| = 5.No update to closestSum.

Step 1 - Outer Loop (i = 1):

  • i = 1 (first element = 2):We pick nums[i] = 2.

Step 2 - Inner Loop (j = 2 to 3):

  • j = 2 (second element = 1):We pick nums[j] = 1.

Step 3 - Inner-Inner Loop (k = 3):

  • k = 3 (third element = -4):We check nums[i] + nums[j] + nums[k] = 2 + 1 - 4 = -1.Calculate the difference: |-1 - 1| = 2.No update to closestSum.

Final Result

After all iterations, the closest sum to the target is 2.

Output: 2

3Sum Closest Code for All Languages - BruteForce
C++ 
class Solution {
public:
    // Function to find the closest sum of triplets to the target
    int threeSumClosest(vector<int>& nums, int target) {
        
        // Initialize closestSum to maximum integer value
        int closestSum = INT_MAX;
        
        // Get the size of the array
        int n = nums.size();
        
        // Step 1: Iterate through each triplet combination
        for (int i = 0; i < n - 2; i++) {
            
            // Iterate through the remaining elements after index i
            for (int j = i + 1; j < n - 1; j++) {
                
                // Iterate through the remaining elements after index j
                for (int k = j + 1; k < n; k++) {
                    
                    // Calculate the sum of the current triplet
                    int currentSum = nums[i] + nums[j] + nums[k];
                    
                    // Step 2: Update closestSum if the current sum is closer to the target
                    if (abs(currentSum - target) < abs(closestSum - target)) {
                        closestSum = currentSum;
                    }
                }
            }
        }
        
        // Return the closest sum
        return closestSum;
    }
};

3Sum Closest code in Java - BruteForce 
class Solution {
    
    // Function to find the closest sum of triplets to the target
    public int threeSumClosest(int[] nums, int target) {
        
        // Initialize closestSum to the maximum integer value
        int closestSum = Integer.MAX_VALUE;
        
        // Get the size of the array
        int n = nums.length;

        // Step 1: Iterate through each triplet combination
        for (int i = 0; i < n - 2; i++) {
            
            // Iterate through the remaining elements after index i
            for (int j = i + 1; j < n - 1; j++) {
                
                // Iterate through the remaining elements after index j
                for (int k = j + 1; k < n; k++) {
                    
                    // Calculate the sum of the current triplet
                    int currentSum = nums[i] + nums[j] + nums[k];

                    // Step 2: Update closestSum if the current sum is closer to the target
                    if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                        closestSum = currentSum;
                    }
                }
            }
        }
        
        // Return the closest sum
        return closestSum;
    }
}

3Sum Closest code in Python - BruteForce 
def three_sum_closest(nums, target):
    
    # Initialize closest_sum to positive infinity
    closest_sum = float('inf')
    
    # Get the length of the input list
    n = len(nums)
    
    # Step 1: Iterate through each triplet combination
    for i in range(n - 2):
        
        # Iterate through the remaining elements after index i
        for j in range(i + 1, n - 1):
            
            # Iterate through the remaining elements after index j
            for k in range(j + 1, n):
                
                # Calculate the sum of the current triplet
                current_sum = nums[i] + nums[j] + nums[k]
                
                # Step 2: Update closest_sum if current sum is closer to target
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
                    
    # Return the closest sum
    return closest_sum

3Sum Closest code in Javascript - BruteForce 
class Solution {
    threeSumClosest(nums, target) {
        // Initialize closestSum to Infinity
        let closestSum = Infinity;
        
        // Get the length of the input array
        let n = nums.length;

        // Step 1: Iterate through each triplet combination
        for (let i = 0; i < n - 2; i++) {
            
            // Iterate through the remaining elements after index i
            for (let j = i + 1; j < n - 1; j++) {
                
                // Iterate through the remaining elements after index j
                for (let k = j + 1; k < n; k++) {
                    
                    // Calculate the sum of the current triplet
                    let currentSum = nums[i] + nums[j] + nums[k];
                    
                    // Step 2: Update closestSum if current sum is closer to target
                    if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                        closestSum = currentSum;
                    }
                }
            }
        }

        // Return the closest sum
        return closestSum;
    }
}

Time Complexity : O(N^3)

The brute force solution involves three nested loops to iterate over all possible triplets in the array. Here's the breakdown:

  1. Outer Loop: Runs from i = 0 to n - 3, which is approximately n iterations.
  2. Second Loop: Runs from j = i + 1 to n - 2, approximately n - i iterations.
  3. Third Loop: Runs from k = j + 1 to n - 1, approximately n - j iterations.

The total number of iterations can be calculated as:
Total Iterations = nC3.
This results in a time complexity of O(n³), where nn is the length of the array.

Space Complexity : O(1)

Auxiliary Space Complexity

The algorithm only uses a few integer variables (closestSum, currentSum, n, and loop counters i, j, k). These require O(1) auxiliary space since no additional data structures are used.

Total Space Complexity

If we consider the input array nums of size n, it requires O(n) space for storage. However, since input storage is not counted in auxiliary space, the total space complexity remains O(n) .

In the brute force approach, we go through all possible groups of three numbers, which takes a lot of time and repeats many checks. To make this faster, we can first arrange the numbers in order and then use a simple method with two pointers. This way, we can quickly find the best combination without checking every single group.

Optimal Approach - (Sorting+Two Pointer)

Intuition

This approach begins by sorting the array, which makes it easier to explore combinations of three numbers efficiently. Sorting arranges the numbers in order, allowing us to use a systematic search method called the two-pointer technique. Instead of checking every possible triplet, we fix one number at a time and use two pointers—one starting just after the fixed number and the other at the end of the array. By adjusting these pointers, we can find combinations of three numbers whose sum is closest to the target.

The idea behind this is simple: when the sum of the three numbers is smaller than the target, moving the left pointer increases the sum. Similarly, when the sum is larger than the target, moving the right pointer decreases the sum. This controlled adjustment avoids redundant checks and leads to a faster solution.

Throughout the process, we maintain a variable closest_sum to track the best sum found so far. Whenever a new sum is closer to the target than the current closest_sum, we update it. If we find a sum exactly equal to the target, we can immediately return it, as no closer sum is possible.

This method is not only more efficient but also intuitive once you see how sorting and the two-pointer technique work together. It reduces the time complexity significantly while ensuring that all possible combinations are considered systematically.

Why do we need to sort the array before using this approach?

Sorting helps us structure the problem so that we can use the two-pointer technique effectively. Once sorted, we can predict the direction of movement—whether to increase or decrease the sum—based on the relative size of the current sum and the target. Without sorting, this directional search wouldn’t be possible.

Can this approach handle negative numbers in the array?

Yes, the approach works for arrays with negative, positive, or mixed numbers. Sorting ensures that all numbers are considered systematically, and the two-pointer logic adjusts for any combination of values.

Approach

Step 1: Sort the Array

Sort the array in ascending order. This helps us systematically adjust the pointers during the search.

Step 2: Initialize Variables

Set a variable closest_sum to a very large value (e.g., infinity) to track the closest sum encountered so far.

Step 3: Iterate Through the Array

Use a loop to fix one number at a time, iterating from index 0 to n−2n−2 (since we need at least three numbers for a triplet).

Step 4: Use Two Pointers

For each fixed number, initialize two pointers:

  • left starts just after the fixed number (i + 1).
  • right starts at the end of the array (len(nums) - 1).
Step 5: Calculate the Current Sum

Add the values at the fixed index, left pointer, and right pointer to get the current sum.

Step 6: Update Closest Sum

If the current_sum is closer to the target than closest_sum, update closest_sum.

Step 7: Adjust Pointers
  • If current_sum is smaller than the target, move the left pointer to the right (left += 1).
  • If current_sum is larger than the target, move the right pointer to the left (right -= 1).
  • If current_sum equals the target, return it immediately, as it's the best possible result.
Step 8: Return Closest Sum

After finishing the loop, return the closest_sum variable, which holds the best sum found.

Let us understand with a video ,

0:00
/2:22

3Sum Closest-Optimal-Approach

3Sum Closest Dry run - Two Pointer

Input: nums = [-1, 2, 1, -4], target = 1
Sort the Array
Sort nums in ascending order:nums = [-4, -1, 1, 2]
Initialize Variables

  • closest_sum = float('inf') (represents an initial large value).

Iterate Through the Array
We iterate through nums using index i.

Iteration 1: i = 0, fixed number = nums[0] = -4

  • Initialize pointers
  • left = 1 (next index after i), pointing to -1.
  • right = 3 (last index), pointing to 2.

Two-Pointer Search
a. Calculate Current Sum:current_sum = nums[i] + nums[left] + nums[right] = -4 + (-1) + 2 = -3
b. Update Closest Sum:Compare |current_sum - target| = |-3 - 1| = 4 with |closest_sum - target| = |inf - 1|.

  • Update closest_sum = -3 (smaller difference).

c. Adjust Pointers:current_sum < target (since -3 < 1), so move left pointer to the right (left = 2).


a. Calculate Current Sum (New):current_sum = nums[i] + nums[left] + nums[right] = -4 + 1 + 2 = -1
b. Update Closest Sum:Compare |-1 - 1| = 2 with |-3 - 1| = 4.

  • Update closest_sum = -1.

c. Adjust Pointers:current_sum < target (since -1 < 1), so move left pointer to the right (left = 3).

At this point, left >= right, so we move to the next iteration.

Iteration 2: i = 1, fixed number = nums[1] = -1

  • Initialize pointers
  • left = 2, pointing to 1.
  • right = 3, pointing to 2.

Two-Pointer Search

a. Calculate Current Sum:current_sum = nums[i] + nums[left] + nums[right] = -1 + 1 + 2 = 2
b. Update Closest Sum:Compare |2 - 1| = 1 with |-1 - 1| = 2.

  • Update closest_sum = 2.

c. Adjust Pointers:current_sum > target (since 2 > 1), so move right pointer to the left (right = 2).
At this point, left >= right, so we finish this iteration.

Return Closest Sum
After finishing all iterations, the closest sum is 2.

3Sum Closest Code for All Languages - Two Pointer
C++ 
class Solution {
public:
    // Function to find the closest sum of triplets to the target
    int threeSumClosest(vector<int>& nums, int target) {
        
        // Step 1: Sort the array
        sort(nums.begin(), nums.end());

        // Step 2: Initialize the closest sum
        int closest_sum = INT_MAX;

        // Step 3: Iterate through the array
        for (int i = 0; i < nums.size() - 2; i++) {
            int left = i + 1, right = nums.size() - 1;

            // Step 4: Use two pointers
            while (left < right) {

                // Step 5: Calculate the current sum
                int current_sum = nums[i] + nums[left] + nums[right];

                // Step 6: Update closest sum if needed
                if (abs(current_sum - target) < abs(closest_sum - target)) {
                    closest_sum = current_sum;
                }

                // Step 7: Adjust pointers
                if (current_sum < target) {
                    left++;  // Move left pointer to the right
                } else if (current_sum > target) {
                    right--;  // Move right pointer to the left
                } else {
                    return current_sum;  // Found exact match
                }
            }
        }

        // Step 8: Return closest sum
        return closest_sum;
    }
};

3Sum Colosest code in Java - Two Pointer 
class Solution {
public:
    // Function to find the closest sum of triplets to the target
    int threeSumClosest(vector<int>& nums, int target) {
        
        // Step 1: Sort the array
        sort(nums.begin(), nums.end());

        // Step 2: Initialize the closest sum
        int closest_sum = INT_MAX;

        // Step 3: Iterate through the array
        for (int i = 0; i < nums.size() - 2; i++) {
            int left = i + 1, right = nums.size() - 1;

            // Step 4: Use two pointers
            while (left < right) {

                // Step 5: Calculate the current sum
                int current_sum = nums[i] + nums[left] + nums[right];

                // Step 6: Update closest sum if needed
                if (abs(current_sum - target) < abs(closest_sum - target)) {
                    closest_sum = current_sum;
                }

                // Step 7: Adjust pointers
                if (current_sum < target) {
                    left++;  // Move left pointer to the right
                } else if (current_sum > target) {
                    right--;  // Move right pointer to the left
                } else {
                    return current_sum;  // Found exact match
                }
            }
        }

        // Step 8: Return closest sum
        return closest_sum;
    }
};

3Sum Colosest code in Python - Two Pointer 
from typing import List
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # Step 1: Sort the array
        nums.sort()
        
        # Step 2: Initialize closest sum with the first triplet
        closest_sum = nums[0] + nums[1] + nums[2]

        # Step 3: Iterate through the array
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1

            # Step 4: Use two pointers
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                # Step 5: Update closest sum if needed
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                # Step 6: Adjust pointers
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum  # Found exact match

        # Step 7: Return closest sum
        return closest_sum

3Sum Colosest code in Javascript - Two Pointer 
function threeSumClosest(nums, target) {
    // Step 1: Sort the array
    nums.sort((a, b) => a - b);

    // Step 2: Initialize closest sum
    let closestSum = Infinity;

    // Step 3: Iterate through the array
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1, right = nums.length - 1;

        // Step 4: Use two pointers
        while (left < right) {
            
            // Step 5: Calculate current sum
            let currentSum = nums[i] + nums[left] + nums[right];

            // Step 6: Update closest sum if needed
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }

            // Step 7: Adjust pointers
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;  // Found exact match
            }
        }
    }
    
    // Step 8: Return closest sum
    return closestSum;
}

Time Complexity : O(N^2)

Sorting the Array:Sorting the array takes O(nlog⁡n), where nn is the size of the array.

Iterating Through the Array:

  • We use a single loop to fix one number, running for n−2 iterations.
  • For each iteration, we use the two-pointer technique, which processes the remaining n−i−1 elements in O(n) time.

Thus, the total time for the two-pointer approach is:

O(n)⋅O(n)=O(n^2)

Overall Time Complexity:The dominating factor is O(n^2) from the two-pointer loop, so the overall complexity is:O(n^2)+O(nlog⁡n)≈O(n^2)

Space Complexity: O(1)

Auxiliary Space Complexity
The algorithm uses a few integer variables (closest_sum, current_sum, i, left, right), which require O(1) space.

Total Space Complexity
The input list nums of size n is required for storage, contributing O(n) space.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

4Sum

Given an array nums of nn integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 ≤ a,b,c,d < n
a,b,c and d are distinct indices
nums[a] + nums[b] + nums[c] + nums[d] = target