How do you solve 3Sum Closest on LeetCode?

3Sum Closest (LeetCode #16) can be solved using Brute Force or Optimal Solution (Two Pointers). The optimal approach is Optimal Solution (Two Pointers) with O(n²) time complexity and O(1) space complexity. Key insight: Sorting the array allows us to use the two-pointer technique, which significantly reduces the number of combinations we need to check.

What is the brute force solution for 3Sum Closest?

The brute force approach for 3Sum Closest is Brute Force, with O(n³) time complexity and O(1) space complexity. The brute force approach involves checking all possible triplets in the array to find the one whose sum is closest to the target. This means we will generate combinations of three numbers and calculate their sums one by one. The optimal Optimal Solution (Two Pointers) approach improves this to O(n²).

What algorithm or data structure is used to solve 3Sum Closest?

3Sum Closest uses the following concepts: Array, Two Pointers, Sorting. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for 3Sum Closest?

When you first see this problem, mention that you will consider both brute force and optimized approaches. Communicate your thought process clearly, especially when explaining how you will use sorting and two pointers. Mention edge cases such as arrays with duplicate values or when the target is less than the smallest possible sum.

What are common mistakes when solving 3Sum Closest?

Students often forget to handle the case where the exact target is found, which can lead to incorrect results. Another common mistake is not sorting the array before applying the two-pointer technique.

#16

3Sum Closest

Medium

ArrayTwo PointersSortingHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Two Pointers)★
Time	O(n³)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution involves sorting the array first and then using a two-pointer technique to efficiently find the closest sum. This reduces the number of combinations we need to check by leveraging the sorted order of the array.

⚙️

Algorithm

6 steps

1Step 1: Sort the array to enable the two-pointer technique.
2Step 2: Initialize a variable to store the closest sum found so far, starting with a large value.
3Step 3: Iterate through the array with an index i, and for each i, set two pointers: left (i + 1) and right (n - 1).
4Step 4: Calculate the sum of the three numbers (nums[i], nums[left], nums[right]).
5Step 5: If the sum is closer to the target than the closest sum, update the closest sum.
6Step 6: Move the pointers based on whether the current sum is less than or greater than the target.

solution.py24 lines

1# Full working Python code with comments
2
3def three_sum_closest(nums, target):
4    nums.sort()  # Sort the array
5    closest_sum = float('inf')  # Initialize closest sum to infinity
6    n = len(nums)
7    for i in range(n):
8        left, right = i + 1, n - 1  # Initialize two pointers
9        while left < right:
10            current_sum = nums[i] + nums[left] + nums[right]
11            # Update closest sum if current sum is closer to target
12            if abs(current_sum - target) < abs(closest_sum - target):
13                closest_sum = current_sum
14            # Move pointers based on comparison with target
15            if current_sum < target:
16                left += 1
17            elif current_sum > target:
18                right -= 1
19            else:
20                return current_sum  # Exact match found
21    return closest_sum
22
23# Example usage
24print(three_sum_closest([-1, 2, 1, -4], 1))  # Output: 2

ℹ

Complexity note: The time complexity is O(n²) because we have a single loop and a nested while loop that runs in linear time. The space complexity is O(1) since we are using a constant amount of space for variables.

1Sorting the array allows us to use the two-pointer technique, which significantly reduces the number of combinations we need to check.
2Always consider edge cases, such as when all numbers are the same or when the target is outside the range of possible sums.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.