3Sum Closest

LeetCode 16 | Difficulty: Medium

Medium

Problem Description

Given an integer array nums of length n and an integer target, find three integers at distinct indices 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.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

- `3 <= nums.length <= 500`

- `-1000 <= nums[i] <= 1000`

- `-10^4 <= target <= 10^4`

Topics: Array, Two Pointers, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

---

Solutions

Solution 1: C# (Best: 179 ms)

Metric	Value
Runtime	179 ms
Memory	N/A
Date	2017-07-24

Solution

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
    Array.Sort(nums);
    int result = nums[0] + nums[1] + nums[nums.Length-1];
    for (int i = 0; i < nums.Length-2; i++)
    {
        int j = i + 1, k = nums.Length - 1;
        while (j < k)
        {
            int sum = nums[i]+nums[j]+nums[k];
            if(sum>target) k--;
            else j++;
            if (Math.Abs(sum - target) < Math.Abs(result - target))
            {
                result = sum;
            }   
        }       
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.