Given an array, Arr of N numbers, and another number target, find three integers in the array such that the sum is closest to the target. Return the sum of the three integers.
Note: If there are multiple solutions, print the maximum one.
Example 1:
Input:
N = 6, target = 2
A[] = {-7,9,8,3,1,1}
Output: 2
Explanation: There is one triplet with sum
2 in the array. Triplet elements are -7,8,
1 whose sum is 2.
Example 2:
Input:
N = 4, target = 13
A[] = {5,2,7,5}
Output: 14
Explanation: There is one triplet with sum
12 and other with sum 14 in the array.
Triplet elements are 5, 2, 5 and 2, 7, 5
respectively. Since abs(13-12) ==
abs(13-14) maximum triplet sum will be
preferred i.e 14.
Your Task:
Complete threeSumClosest() function and return the expected answer.
Expected Time Complexity: O(N*N).
Expected Auxiliary Space: O(1).
Constraints:
3 ≤ N ≤ 10^{3}
-10^{5} ≤ A[i] ≤ 10^{5}
1 ≤ target ≤ 10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N*N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



# arr    : list of integers denoting the elements of the array

# target : as specified in the problem statement



class Solution:

    def threeSumClosest (self, arr, target):

    # Your Code Here

Solutions:
class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		r = sum(arr[:3])
		for i in range(len(arr) - 2):
			s = i + 1
			l = len(arr) - 1
			while s < l:
				su = arr[i] + arr[s] + arr[l]
				if abs(target - su) < abs(target - r):
					r = su
				elif abs(target - su) == abs(target - r):
					r = max(r, su)
				if su < target:
					s += 1
				else:
					l -= 1
		return r


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		n = len(arr)
		ans = []
		temp = []
		for i in range(n - 2):
			a = i + 1
			b = n - 1
			while a < b:
				x = arr[i] + arr[a] + arr[b]
				if x == target:
					return target
				elif x > target:
					ans.append(x)
					temp.append(abs(x - target))
					b -= 1
				else:
					ans.append(x)
					temp.append(abs(x - target))
					a += 1
		t1 = min(temp) + target
		t2 = target - min(temp)
		if t1 in ans:
			return t1
		return t2


class Solution:

	def threeSumClosest(self, arr, target):
		n = len(arr)
		arr = sorted(arr)
		minDiff = 1000000007
		res = -1000000007
		for i in range(n):
			sp = i + 1
			ep = n - 1
			while sp < ep:
				sum = arr[i] + arr[sp] + arr[ep]
				curDiff = abs(target - sum)
				if curDiff == minDiff:
					res = max(res, sum)
				elif curDiff < minDiff:
					minDiff = curDiff
					res = sum
				if sum == target:
					break
				elif sum > target:
					ep -= 1
				else:
					sp += 1
		return res


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		N = len(arr)
		Sum = 10000000000.0
		for i in range(N - 2):
			a = arr[i]
			L = i + 1
			R = N - 1
			while L < R:
				temp = a + arr[L] + arr[R]
				if temp == target:
					return target
				elif temp > target:
					R -= 1
				else:
					L += 1
				if abs(temp - target) < abs(Sum - target):
					Sum = temp
				elif abs(temp - target) == abs(Sum - target) and temp > Sum:
					Sum = temp
		return Sum


class Solution:

	def __init__(self):
		self.INT_MAX = 1000000

	def threeSumClosest(self, array, target):
		abs1 = ans2 = self.INT_MAX
		N = len(array)
		array.sort()
		result = dict()
		for i in range(N - 2):
			start = i + 1
			end = N - 1
			while start < end:
				temp = array[i] + array[start] + array[end]
				if temp == target:
					return temp
				elif temp > target:
					if abs(temp - target) < ans2:
						ans2 = abs(temp - target)
						ans1 = temp
					elif abs(temp - target) == ans2:
						ans1 = max(ans1, temp)
					end -= 1
				else:
					if abs(temp - target) < ans2:
						ans1 = temp
						ans2 = abs(temp - target)
					elif abs(temp - target) == ans2:
						ans1 = max(ans1, temp)
					start += 1
		return ans1


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		sum = 0
		result = target * 3
		for x in range(len(arr) - 2):
			start = x + 1
			end = len(arr) - 1
			while start < end:
				sum = arr[x] + arr[start] + arr[end]
				if abs(target - sum) == abs(target - result):
					result = max(sum, result)
				elif abs(target - sum) < abs(target - result):
					result = sum
				if sum < target:
					start += 1
				else:
					end -= 1
		return result


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		ans = 0
		diff = float('inf')
		for i in range(n - 2):
			j = i + 1
			k = len(arr) - 1
			while j < k:
				if arr[i] + arr[j] + arr[k] == target:
					return target
				if abs(arr[i] + arr[j] + arr[k] - target) < abs(target - diff):
					diff = arr[i] + arr[j] + arr[k]
				if abs(arr[i] + arr[j] + arr[k] - target) == abs(target - diff):
					diff = max(arr[i] + arr[j] + arr[k], diff)
				if arr[i] + arr[j] + arr[k] > target:
					k -= 1
				else:
					j += 1
		return diff


class Solution:

	def threeSumClosest(self, arr, target):
		cd = float('inf')
		arr.sort()
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				summ = arr[i] + arr[left] + arr[right]
				if summ == target:
					return target
				elif summ > target:
					right -= 1
				else:
					left += 1
				d = abs(target - summ)
				if d < cd:
					cd = d
					ret = summ
				elif d == cd:
					ret = max(ret, summ)
		return ret


class Solution:

	def threeSumClosest(self, arr, target):
		clss = float('inf')
		arr.sort()
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				curs = arr[i] + arr[left] + arr[right]
				if curs == target:
					return target
				elif curs > target:
					right -= 1
				else:
					left += 1
				if abs(curs - target) < abs(clss - target):
					clss = curs
				elif abs(curs - target) == abs(clss - target) and curs > clss:
					clss = curs
		return clss


class Solution:

	def threeSumClosest(self, arr, target):
		n = len(arr)
		if n == 3:
			return sum(arr)
		ans = -float('inf')
		arr.sort()
		for i in range(n - 2):
			start = i + 1
			end = n - 1
			while start < end:
				summ = arr[i] + arr[start] + arr[end]
				if target == summ:
					return target
				if abs(target - summ) < abs(target - ans):
					ans = summ
				elif abs(target - summ) == abs(target - ans):
					ans = max(summ, ans)
				if summ > target:
					end -= 1
				else:
					start += 1
		return ans


import sys

class Solution:

	def threeSumClosest(self, arr, target):
		maxi = sys.maxsize
		ans = 0
		arr.sort()
		for i in range(len(arr) - 2):
			l = i + 1
			r = len(arr) - 1
			while l < r:
				sumi = arr[i] + arr[l] + arr[r]
				if sumi == target:
					return target
				if abs(sumi - target) < abs(target - maxi):
					maxi = sumi
				if abs(sumi - target) == abs(target - maxi):
					maxi = max(sumi, maxi)
				if sumi > target:
					r -= 1
				else:
					l += 1
		return maxi


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		minsum = 10 ** 9
		ans = 0
		for i in range(len(arr)):
			first = arr[i]
			start = i + 1
			end = n - 1
			while start < end:
				summ = first + arr[start] + arr[end]
				if summ == target:
					return summ
				if abs(target - summ) < abs(target - minsum):
					minsum = summ
				if abs(target - summ) == abs(target - minsum):
					minsum = max(summ, minsum)
				if summ > target:
					end -= 1
				else:
					start += 1
		return minsum


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		closest_sum = sum(arr[:3])
		for i in range(len(arr) - 2):
			j = i + 1
			k = len(arr) - 1
			while j < k:
				current_sum = arr[i] + arr[j] + arr[k]
				if abs(target - current_sum) < abs(target - closest_sum):
					closest_sum = current_sum
				elif abs(target - current_sum) == abs(target - closest_sum):
					closest_sum = max(closest_sum, current_sum)
				if current_sum < target:
					j += 1
				else:
					k -= 1
		return closest_sum


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		ans = sum(arr[:3])
		for (i, j) in enumerate(arr[:-2]):
			a = i + 1
			b = len(arr) - 1
			while a < b:
				temp = j + arr[a] + arr[b]
				if temp == target:
					return temp
				X = abs(temp - target)
				Y = abs(ans - target)
				if X == Y:
					ans = max(ans, temp)
				elif X < Y:
					ans = temp
				if temp < target:
					a += 1
				elif temp > target:
					b -= 1
		return ans


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		n = len(arr)
		res = sum(arr[:3])
		for (i, v) in enumerate(arr[:-2]):
			l = i + 1
			r = len(arr) - 1
			len(arr) - 1
			while l < r:
				temp = v + arr[l] + arr[r]
				if temp == target:
					return temp
				A = abs(temp - target)
				B = abs(res - target)
				if A == B:
					res = max(res, temp)
				elif A < B:
					res = temp
				if temp < target:
					l += 1
				elif temp > target:
					r -= 1
		return res


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		x = sum(arr[:3])
		n = len(arr)
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				ans = arr[i] + arr[j] + arr[k]
				y = target - ans
				z = target - x
				if abs(y) < abs(z):
					x = ans
				elif abs(y) == abs(z):
					x = max(x, ans)
				if ans < target:
					j += 1
				else:
					k -= 1
		return x


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		l = len(arr)
		w = abs(sum(arr[:3]) - target)
		mx = 0
		for i in range(l - 2):
			a = i + 1
			b = l - 1
			while a < b:
				p = [arr[i], arr[a], arr[b]]
				p1 = sum(p)
				p2 = abs(p1 - target)
				if p2 <= w:
					if p2 == w:
						if mx < p1:
							mx = p1
					else:
						w = p2
						mx = p1
				if target > p1:
					a += 1
				else:
					b -= 1
		return mx


from typing import List

class Solution:

	def threeSumClosest(self, nums: List[int], target: int) -> int:
		nums.sort()
		n = len(nums)
		closest_sum = float('inf')
		min_diff = float('inf')
		for i in range(n):
			(l, r) = (i + 1, n - 1)
			while l < r:
				cur_sum = nums[i] + nums[l] + nums[r]
				cur_diff = abs(target - cur_sum)
				if cur_diff < min_diff:
					min_diff = cur_diff
					closest_sum = cur_sum
				elif cur_diff == min_diff:
					closest_sum = max(closest_sum, cur_sum)
				if cur_sum == target:
					return target
				elif cur_sum < target:
					l += 1
				else:
					r -= 1
		return closest_sum


class Solution:

	def threeSumClosest(self, arr, target):
		l = len(arr)
		sum = 0
		min_sum = []
		max_sum = []
		arr.sort()
		for i in range(l - 2):
			left = i + 1
			right = l - 1
			while left < right:
				sum = arr[i] + arr[left] + arr[right]
				if sum == target:
					return target
				elif sum > target:
					max_sum.append(sum)
					right -= 1
				else:
					min_sum.append(sum)
					left += 1
		a = b = 0
		if max_sum:
			a = min(max_sum)
			res = a
		if min_sum:
			b = max(min_sum)
			res = b
		if max_sum and min_sum:
			if a - target > target - b:
				res = b
			else:
				res = a
		return res


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		n = len(arr)
		diff = float('inf')
		output = 0
		for i in range(n - 2):
			k = n - 1
			for j in range(i + 1, n - 1):
				while j < k and arr[i] + arr[j] + arr[k] > target:
					summa = arr[i] + arr[j] + arr[k]
					if summa - target < diff or (summa - target == diff and summa > output):
						diff = summa - target
						output = summa
					k -= 1
				if j == k:
					break
				summa = arr[i] + arr[j] + arr[k]
				if abs(summa - target) < diff or (summa - target == diff and summa > output):
					diff = abs(summa - target)
					output = summa
		return output


import sys

class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		closestsum = sys.maxsize
		n = len(arr)
		for i in range(n - 2):
			ptr1 = i + 1
			ptr2 = n - 1
			while ptr1 < ptr2:
				sum = arr[i] + arr[ptr1] + arr[ptr2]
				if sum == target:
					return sum
				elif sum < target:
					if abs(target - sum) < abs(target - closestsum):
						closestsum = sum
					elif abs(target - sum) == abs(target - closestsum):
						closestsum = max(closestsum, sum)
					ptr1 += 1
				else:
					if abs(target - sum) < abs(target - closestsum):
						closestsum = sum
					elif abs(target - sum) == abs(target - closestsum):
						closestsum = max(closestsum, sum)
					ptr2 -= 1
		return closestsum


class Solution:

	def threeSumClosest(self, arr, target):
		m = 100000000.0
		arr.sort()
		n = len(arr)
		for i in range(n):
			l = i + 1
			r = n - 1
			while l < r:
				temp = arr[i] + arr[l] + arr[r]
				if temp == target:
					return temp
				elif temp < target:
					if abs(temp - target) < abs(m - target):
						m = temp
					elif abs(temp - target) == abs(m - target):
						m = max(m, temp)
					l += 1
				else:
					if abs(temp - target) < abs(m - target):
						m = temp
					elif abs(temp - target) == abs(m - target):
						m = max(m, temp)
					r -= 1
		return m


class Solution:

	def threeSumClosest(self, a, target):
		arr.sort()
		k1 = -1
		m = 10 ** 9
		for i in range(len(arr)):
			(j, k) = (i + 1, len(arr) - 1)
			while k > j:
				if arr[i] + arr[j] + arr[k] == target:
					return a[i] + a[j] + a[k]
				if arr[i] + arr[j] + arr[k] < target:
					if m == abs(target - (arr[i] + arr[j] + arr[k])):
						k1 = max(k1, arr[i] + arr[j] + arr[k])
					if m > abs(target - arr[i] - arr[j] - arr[k]):
						k1 = arr[i] + arr[j] + arr[k]
						m = abs(target - (arr[i] + arr[j] + arr[k]))
					j = j + 1
					continue
				if arr[i] + arr[j] + arr[k] > target:
					if m == abs(target - (arr[i] + arr[j] + arr[k])):
						k1 = max(k1, arr[i] + arr[j] + arr[k])
					if m > abs(target - (arr[i] + arr[j] + arr[k])):
						k1 = arr[i] + arr[j] + arr[k]
						m = abs(target - (arr[i] + arr[j] + arr[k]))
					k = k - 1
		return k1


class Solution:

	def threeSumClosest(self, arr, target):
		ans = []
		temp = []
		for i in range(0, len(arr)):
			for j in range(i + 1, len(arr)):
				for k in range(j + 1, len(arr)):
					x = arr[i] + arr[j] + arr[k]
					if x == target:
						return target
					elif x > target:
						ans.append(x)
						temp.append(abs(x - target))
					else:
						ans.append(x)
						temp.append(abs(x - target))
		t1 = min(temp) + target
		t2 = target - min(temp)
		if t1 in ans:
			return t1
		return t2


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		res = -1000000000.0
		for i in range(len(arr)):
			(j, k) = (0, len(arr) - 1)
			cs = 0
			while j < k:
				if j == i:
					j += 1
					continue
				elif k == i:
					k -= 1
					continue
				cs = arr[i] + arr[j] + arr[k]
				if abs(res - target) > abs(cs - target):
					res = cs
				elif abs(target - cs) == abs(target - res):
					res = max(cs, res)
				if cs < target:
					j += 1
				elif cs > target:
					k -= 1
				else:
					return cs
		return res


class Solution:

	def threeSumClosest(self, arr, target):
		n = len(arr)
		diff = 9999999999
		arr.sort()
		sum_three = 0
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				three_sum = arr[i] + arr[j] + arr[k]
				if abs(three_sum - target) == diff:
					if three_sum > target:
						sum_three = three_sum
				elif abs(three_sum - target) < diff:
					diff = abs(three_sum - target)
					sum_three = three_sum
				if three_sum >= target:
					k -= 1
				else:
					j += 1
		return sum_three


class Solution:

	def threeSumClosest(self, A, X):
		n = len(A)
		A.sort()
		ans = 0
		diff = 10 ** 9
		for i in range(n):
			s = i + 1
			e = n - 1
			while s < e:
				sum = A[i] + A[s] + A[e]
				if sum == X:
					return X
				if abs(X - sum) < diff:
					diff = min(diff, abs(X - sum))
					ans = sum
				if abs(X - sum) == diff:
					ans = max(ans, sum)
				if sum > X:
					e -= 1
				elif sum < X:
					s += 1
		return ans


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		close_sum = 10 ** 5
		for i in range(len(arr)):
			l = i + 1
			r = len(arr) - 1
			while l < r:
				current_sum = arr[i] + arr[l] + arr[r]
				if abs(current_sum - target) == abs(close_sum - target) and current_sum > close_sum:
					close_sum = current_sum
				if current_sum < target:
					l += 1
				else:
					r -= 1
				if abs(current_sum - target) < abs(close_sum - target):
					close_sum = current_sum
		return close_sum


class Solution:

	def threeSumClosest(self, arr, target):
		n = len(arr)
		arr.sort()
		res = float('-inf')
		for (i, v) in enumerate(arr[:-2]):
			if i and arr[i] == arr[i - 1]:
				continue
			(l, r) = (i + 1, len(arr) - 1)
			while l < r:
				temp = v + arr[l] + arr[r]
				if temp == target:
					return temp
				(A, B) = (abs(temp - target), abs(res - target))
				if A == B:
					res = max(res, temp)
				if A < B:
					res = temp
				if temp < target:
					l += 1
				elif temp > target:
					r -= 1
		return res


class Solution:

	def threeSumClosest(self, a, target):
		a = sorted(a)
		n = len(a)
		cs = a[0] + a[1] + a[2]
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				s = a[i] + a[l] + a[r]
				if abs(target - s) < abs(target - cs):
					cs = s
				if abs(target - s) == abs(target - cs):
					cs = cs if cs > s else s
				if s > target:
					r -= 1
				else:
					l += 1
		return cs


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		c = -9999999
		n = len(arr)
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				s = arr[i] + arr[j] + arr[k]
				if abs(target - s) < abs(target - c):
					c = s
				elif abs(target - s) == abs(target - c):
					c = max(c, s)
				if s > target:
					k -= 1
				else:
					j += 1
		return c


import sys

class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		closestSum = sys.maxsize
		for i in range(len(arr) - 2):
			left = i + 1
			right = len(arr) - 1
			while left < right:
				currentSum = arr[i] + arr[left] + arr[right]
				if abs(target - currentSum) < abs(target - closestSum):
					closestSum = currentSum
				elif abs(target - currentSum) == abs(target - closestSum):
					closestSum = max(closestSum, currentSum)
				if currentSum > target:
					right -= 1
				elif currentSum < target:
					left += 1
				else:
					return currentSum
		return closestSum


import sys

class Solution:

	def threeSumClosest(self, arr, x):
		arr.sort()
		closestSum = sys.maxsize
		for i in range(len(arr) - 2):
			ptr1 = i + 1
			ptr2 = len(arr) - 1
			while ptr1 < ptr2:
				sum = arr[i] + arr[ptr1] + arr[ptr2]
				if abs(x - sum) < abs(x - closestSum):
					closestSum = sum
				elif abs(x - sum) == abs(x - closestSum):
					closestSum = max(closestSum, sum)
				if sum > x:
					ptr2 -= 1
				else:
					ptr1 += 1
		return closestSum


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		result = []
		minn = 99999999999
		n = len(arr)
		for i in range(n - 2):
			low = i + 1
			high = n - 1
			while low < high:
				sm = arr[i] + arr[low] + arr[high]
				if sm == target:
					return target
				elif sm < target:
					low += 1
				else:
					high -= 1
				if abs(sm - target) < minn:
					minn = abs(sm - target)
					result = [sm]
				elif abs(sm - target) == minn:
					result.append(sm)
		return max(result)


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		n = len(arr)
		minn = 9999999999
		result = []
		for i in range(n - 2):
			(j, k) = (i + 1, n - 1)
			while j < k:
				sm = arr[i] + arr[j] + arr[k]
				if sm == target:
					return target
				elif sm < target:
					j += 1
				elif sm > target:
					k -= 1
				if abs(sm - target) < minn:
					minn = abs(sm - target)
					result = [sm]
				elif abs(sm - target) == minn:
					result.append(sm)
		return max(result)


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		n = len(arr)
		a = []
		temp = []
		for i in range(n - 2):
			lr = i + 1
			rl = n - 1
			while lr < rl:
				x = arr[i] + arr[lr] + arr[rl]
				if x == target:
					return target
				elif x < target:
					a.append(x)
					temp.append(abs(x - target))
					lr += 1
				else:
					a.append(x)
					temp.append(abs(x - target))
					rl -= 1
		res1 = min(temp) + target
		res2 = target - min(temp)
		if res1 in a:
			return res1
		else:
			return res2


def closest(arr, n, target, idx):
	mx = 10 ** 10
	(start, end) = (idx + 1, n - 1)
	while start < end and start < n and (end > idx):
		s = arr[start] + arr[end]
		if abs(s - target) < abs(mx - target):
			mx = s
		elif abs(s - target) == abs(mx - target):
			mx = max(mx, s)
		if s > target:
			end -= 1
		elif s < target:
			start += 1
		elif s == target:
			return s
	return mx

class Solution:

	def threeSumClosest(self, arr, target):
		mx = 10 ** 10
		arr.sort()
		for i in range(len(arr) - 2):
			res = arr[i] + closest(arr, len(arr), target - arr[i], i)
			if abs(res - target) < abs(mx - target):
				mx = res
			elif abs(res - target) == abs(mx - target):
				mx = max(mx, res)
		return mx


class Solution:

	def threeSumClosest(self, arr, target):
		import sys
		diff = sys.maxsize
		res = 0
		arr = sorted(arr)
		for i in range(len(arr) - 2):
			l = i + 1
			r = len(arr) - 1
			while l < r:
				temp_sum = arr[i] + arr[l] + arr[r]
				if temp_sum == target:
					return target
				elif temp_sum > target:
					if temp_sum - target < diff:
						res = temp_sum
						diff = temp_sum - target
					elif temp_sum - target == diff:
						res = temp_sum
					r -= 1
				else:
					if target - temp_sum < diff:
						res = temp_sum
						diff = target - temp_sum
					l += 1
		return res


class Solution:

	def threeSumClosest(self, arr, target):
		arr = sorted(arr)
		closestSum = 100001
		for i in range(len(arr) - 2):
			ptr1 = i + 1
			ptr2 = len(arr) - 1
			while ptr1 < ptr2:
				sum = arr[i] + arr[ptr1] + arr[ptr2]
				if abs(target - sum) < abs(target - closestSum):
					closestSum = sum
				if abs(target - sum) == abs(target - closestSum):
					if sum > closestSum:
						closestSum = sum
				if sum > target:
					ptr2 -= 1
				else:
					ptr1 += 1
		return closestSum


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		distance = float('inf')
		for x in range(len(arr) - 2):
			(l, r) = (x + 1, len(arr) - 1)
			while l < r:
				sum_val = arr[x] + arr[l] + arr[r]
				if abs(sum_val - target) < abs(distance - target):
					distance = sum_val
				elif abs(sum_val - target) == abs(distance - target):
					distance = max(distance, sum_val)
				if sum_val < target:
					l += 1
				else:
					r -= 1
		return distance


class Solution:

	def threeSumClosest(self, arr, target):
		arr.sort()
		c = 2147483647
		result = 0
		for i in range(len(arr)):
			ptr1 = i + 1
			ptr2 = len(arr) - 1
			while ptr1 < ptr2:
				summ = arr[i] + arr[ptr1] + arr[ptr2]
				if summ == target:
					return target
				if summ < target:
					if abs(target - summ) < c:
						result = summ
						c = abs(target - summ)
					ptr1 += 1
				else:
					if abs(target - summ) <= c:
						result = summ
						c = abs(target - summ)
					ptr2 -= 1
		return result