Is 3Sum Closest easy or hard?

3Sum Closest is typically classified as a medium difficulty problem. The logic becomes straightforward once you recognize the connection to the classic 3Sum problem and apply sorting with a two-pointer scan.

How to solve 3Sum Closest in O(n)?

Solving 3Sum Closest in strict O(n) time is not possible for the general case because every element can potentially form combinations with two others. The best known practical approach is O(n^2) using sorting and the two-pointer technique.

What is the best approach for 3Sum Closest?

The best approach is sorting the array followed by a two-pointer scan. After fixing one element, move two pointers from both ends of the remaining array to adjust the sum toward the target. This runs in O(n^2) time and O(1) extra space and is the solution most interviewers expect.

3Sum Closest Python or Java solution pattern

Most Python and Java implementations follow the same pattern: sort the array, iterate with index i, and apply two pointers left and right to compute candidate sums. Update the closest sum whenever a smaller difference from the target is found. The algorithm runs in O(n^2) time.

What data structure is used in 3Sum Closest?

The primary structures involved are arrays and pointer indices. The optimal approach relies on sorting the array and then using two pointers to scan inward. Some alternative implementations use a hashmap or hash set to store complements during iteration.

What is the time complexity of 3Sum Closest?

The optimal solution runs in O(n^2) time. Sorting takes O(n log n), and for each element you perform a linear two-pointer scan across the rest of the array. The space complexity is O(1) beyond the input array.

Is 3Sum Closest asked at Google, Amazon, or Meta interviews?

3Sum Closest appears in interviews at companies such as Amazon, Meta, and Google because it tests array manipulation, sorting, and two-pointer reasoning. Interviewers often use it to evaluate whether candidates can adapt the classic 3Sum pattern to a slightly different objective.

Description Solution Video 6:25

16. 3Sum Closest

Medium47.4% acceptance11 companies

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
-10⁴ <= target <= 10⁴

Asked at 11 companies

Harness Dream11 Meta

Google Amazon Bloomberg Zoho Flipkart Bytedance Microsoft

TCS

Topics

6:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

16. 3Sum Closest

Asked at 11 companies

Topics

Similar problems