Closest Three Sum

JavaView on GFG

Time: O(n^2)

Space: O(1)

Intuition

Find triplet with sum closest to target. Sort + two pointers for each anchor.

Algorithm

1Sort. For each i: two pointers l=i+1, r=n-1. Track minimum |sum-target|. Move pointers based on comparison.

Common Pitfalls

•Same as LC 16. Sort first. Update closest on each iteration. Early exit if exact match found.

Closest Three Sum.java

Java

// Approach: Sort array. For each element, use two pointers on the remaining array to find the closest sum to target.
// Time: O(n^2) Space: O(1)
import java.util.*;

class Solution {
    static int threeSumClosest(int[] ar, int target) {
        Arrays.sort(ar);
        int ms = ar[0] + ar[1] + ar[ar.length - 1];

        for (int i = 0; i < ar.length - 1; i++) {
            int s = i + 1;
            int e = ar.length - 1;

            while (s < e) {

                int sum = ar[i] + ar[e] + ar[s];
                int dif = Math.abs(sum - target);

                if (dif < Math.abs(ms - target)) {

                    ms = sum;
                } else if (dif == Math.abs(ms - target) && sum > ms) {
                    ms = sum;
                }

                if (sum > target)
                    e--;
                else
                    s++;

            }

        }
        return ms;

    }
}

Was this solution helpful?