3Sum Closest

3Sum Closest is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

Problem statement

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

- -104 <= target <= 104

Topics and companies

Topics: Array, Two Pointers, Sorting.

Reported in interviews at Amazon, Apple, Google, Facebook, Bloomberg.

How to practise 3Sum Closest on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(1) space.

Open 3Sum Closest in the code editor, or read the 3Sum Closest editorial for a worked solution with its approach and complexity analysis.

Where 3Sum Closest sits in the DSA pattern sheet

• Two Pointers pattern guide
• Converging (Sorted Array Target Sum) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to 3Sum Closest

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

• Boats to Save People — Medium, same subpattern
• Container With Most Water — Medium, same subpattern
• 4Sum — Medium, same subpattern
• Squares of a Sorted Array — Easy, same subpattern
• 3Sum Smaller — Medium, same subpattern
• 3Sum — Medium, same subpattern