How do you solve 3Sum on LeetCode?

3Sum (LeetCode #15) 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 efficiently use the two-pointer technique, which reduces the number of checks needed for pairs.

What is the brute force solution for 3Sum?

The brute force approach for 3Sum 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 see if they sum to zero. This is straightforward but can be inefficient for larger arrays. The optimal Optimal Solution (Two Pointers) approach improves this to O(n²).

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

3Sum 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?

When you first see this problem, mention the brute force approach to show your understanding of the problem, then transition to the optimal solution. Communicate your thought process clearly, especially when discussing how you would handle duplicates and the two-pointer technique. Mention edge cases like arrays with fewer than three elements, all zeros, or arrays with no valid triplets.

What are common mistakes when solving 3Sum?

Failing to sort the array before applying the two-pointer technique, leading to incorrect results. Not handling duplicates properly, which can cause the same triplet to be counted multiple times.

#15

3Sum

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)

By sorting the array first, we can use a two-pointer technique to find pairs that sum to a specific value, which allows us to efficiently find triplets that sum to zero.

⚙️

Algorithm

3 steps

1Step 1: Sort the array.
2Step 2: Iterate through the array, fixing one element at a time.
3Step 3: Use two pointers to find pairs that sum to the negative of the fixed element.

solution.py28 lines

1# Full working Python code with comments
2
3def three_sum(nums):
4    nums.sort()
5    result = []
6    n = len(nums)
7    for i in range(n):
8        if i > 0 and nums[i] == nums[i - 1]:
9            continue  # Skip duplicates
10        left, right = i + 1, n - 1
11        while left < right:
12            total = nums[i] + nums[left] + nums[right]
13            if total < 0:
14                left += 1
15            elif total > 0:
16                right -= 1
17            else:
18                result.append([nums[i], nums[left], nums[right]])
19                while left < right and nums[left] == nums[left + 1]:
20                    left += 1  # Skip duplicates
21                while left < right and nums[right] == nums[right - 1]:
22                    right -= 1  # Skip duplicates
23                left += 1
24                right -= 1
25    return result
26
27# Example usage
28print(three_sum([-1, 0, 1, 2, -1, -4]))

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loop for the two-pointer approach. The space complexity is O(1) since we are using only a constant amount of extra space.

1Sorting the array allows us to efficiently use the two-pointer technique, which reduces the number of checks needed for pairs.
2Skipping duplicates is crucial in both the brute force and optimal solutions to ensure unique triplets.

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