3Sum Closest: O(n²) Two-Pointer Magic 🚀 leetcode: 16

Three Sum Closest - LeetCode Solution

In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference.

Problem Statement

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.

Intuition

The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique.

• Sorting: First, sort the array. This allows us to use the two-pointer approach to efficiently find the triplet.
• Two-pointer technique: For each element in the array, treat it as the first element of the triplet. Then, use two pointers (one at the start and one at the end of the remaining array) to find the other two elements that, when added to the first element, give a sum closest to the target.
• Update the closest sum: As we iterate through the array, we keep track of the sum that is closest to the target. If we find a sum that is exactly equal to the target, we can return it immediately.

Approach

Here's the step-by-step approach to solve the problem:

1. Sort the array: This helps in efficiently finding the triplet using the two-pointer approach.
2. Initialize the result: Start with a large value (sys.maxsize - 1) to keep track of the closest sum.
3. Iterate through the array: For each element in the array (up to the third last element), treat it as the first element of the triplet.
4. Two-pointer search: Use two pointers, one at the start (just after the current element) and one at the end of the array. Move these pointers towards each other to find the sum closest to the target.
5. Update the closest sum: If the current sum is closer to the target than the previously recorded sum, update the result.
6. Return the result: After iterating through the array, return the sum that is closest to the target.

Complexity Analysis

• Time Complexity: O(n²), where n is the length of the array. The sorting step takes O(n log n), and the two-pointer approach takes O(n²) in the worst case.
• Space Complexity: O(1) or O(n) depending on the sorting algorithm used. The two-pointer approach uses constant extra space.

Solution Code

Below is the Python implementation of the solution:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        result = sys.maxsize - 1
        if n == 3:
            return sum(nums)
        
        for i in range(n - 2):
            start = i + 1
            end = n - 1
            while start < end:
                total = nums[i] + nums[start] + nums[end]
                if total == target:
                    return total
                elif total < target:
                    if abs(result - target) > abs(total - target):
                        result = total
                    start += 1
                else:
                    if abs(result - target) > abs(total - target):
                        result = total
                    end -= 1
        return result

Explanation

- Sorting: The array is sorted to make it easier to find the triplet using the two-pointer approach.
- Two-pointer technique: For each element in the array, we use two pointers to find the other two elements that, when added to the current element, give a sum closest to the target.
- Updating the result: We keep updating the result whenever we find a sum that is closer to the target than the previously recorded sum.
- Returning the result: After iterating through the array, we return the sum that is closest to the target.

LeetCode Solution Link

You can find my detailed LeetCode solution for this problem here: LeetCode Solution.

Conclusion

The Three Sum Closest problem is a great example of how sorting and the two-pointer technique can be combined to solve complex problems efficiently. By understanding the intuition and approach, you can tackle similar problems with confidence. Happy coding!