Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

3Sum Closest

Medium · Hashing & Two Pointers · Asked at Amazon, Meta, Google, Microsoft

Choose three elements at different indices whose sum is closest to target, and print that sum. If two sums are equally close, print the smaller one.

Input

First line: n target. Second line: n integers.

Output

The closest sum.

Constraints

Sort, fix the first element, then move two pointers over the rest — O(n²).

Example 1

Input

4 1
-1 2 1 -4

Output

2

Example 2

Input

3 1
0 0 0

Output

0

Hints

  1. Sort the array. Fix the first element i, then look for the best pair in the part after i.
  2. With two pointers, if the current sum is below the target move the left pointer up, otherwise move the right pointer down. Update the best sum each time (smaller sum wins ties).

Approach

After sorting, for each i set l = i+1, r = n−1. The sum a[i] + a[l] + a[r] is compared with the best so far (closer distance wins; on equal distance keep the smaller sum). If the sum equals the target, it is optimal. If it is smaller, increasing l is the only way to get closer; if larger, decrease r. This explores every useful pair for each i in O(n).

Complexity: O(n²) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long t;
    cin >> n >> t;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    long long best = a[0] + a[1] + a[2];
    for (int i = 0; i < n - 2; i++) {
        int l = i + 1, r = n - 1;
        while (l < r) {
            long long s = a[i] + a[l] + a[r];
            long long ds = llabs(s - t), db = llabs(best - t);
            if (ds < db || (ds == db && s < best)) best = s;
            if (s < t) l++;
            else if (s > t) r--;
            else break;
        }
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, t = data[0], data[1]
a = sorted(data[2 : 2 + n])
best = a[0] + a[1] + a[2]
for i in range(n - 2):
    l, r = i + 1, n - 1
    while l < r:
        s = a[i] + a[l] + a[r]
        if (abs(s - t), s) < (abs(best - t), best):
            best = s
        if s < t:
            l += 1
        elif s > t:
            r -= 1
        else:
            break
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long t = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        Arrays.sort(a);
        long best = a[0] + a[1] + a[2];
        for (int i = 0; i < n - 2; i++) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                long s = a[i] + a[l] + a[r];
                long ds = Math.abs(s - t), db = Math.abs(best - t);
                if (ds < db || (ds == db && s < best)) best = s;
                if (s < t) l++;
                else if (s > t) r--;
                else break;
            }
        }
        System.out.println(best);
    }
}

Solve 3Sum Closest online · All practice problems