**Solution**

**3Sum Closest** https://leetcode.com/problems/3sum-closest/

**Brute-force: O(N^3)**

- Brute force solution will be O(N^3). We end up testing every subset and update the closest sum in every iteration.

**Two Pointer Solution: O(N^2)**

- We can use the two pointer method to reduce complexity to O(N^2). We begin by sorting the array.
- Now we use three indices i,j and k. We iterate i from 0 to N (actually till N-2 is fine). We initialize j to i+1 and k to N-1.
- Now we compute curr_sum = nums[i]+nums[j]+nums[k]. If this equals target, we have the closest sum.
- Otherwise update closest_sum using the rule abs(curr_sum-target) < abs(closest_sum-target).
- Now what if curr_sum is less than target. Should we test (nums[i]+nums[j]+nums[k-1]), (nums[i]+nums[j]+nums[k-2]), (nums[i]+nums[j]+nums[k-3]) ? The answer is NO. All of these triplets will be less than curr_sum. And curr_sum is less than target - so there is no point testing these triplets. We must move forward by advancing j to j + 1 in the hope to get a larger triplet. This is the main intuition in this problem.
- You can visualize (6) by thinking all possible triplet sums sorted and arranged on a number line. When you find a curr_sum less than target, you increase curr_sum by increasing j. When you find a curr_sum less more than target, you reduce curr_sum by reducing k

```
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
closest_sum = 2**31-1
for i in range(len(nums)):
j,k = i+1, len(nums)-1
while j<k:
curr_sum = nums[i] + nums[j] + nums[k]
if curr_sum == target:
return curr_sum
if abs(curr_sum-target) < abs(closest_sum-target):
closest_sum = curr_sum
if curr_sum < target:
j = j+1
else:
k = k-1
return closest_sum
```