3Sum

Mediumtwo-pointersarraysorting
Category: Two Pointers
Companies that ask this question:
AmazonFacebookMicrosoftGoogleApple
LeetCode →NeetCode →

Approach

3Sum

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Examples

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Intuition

The key insight is to reduce 3Sum to a Two Sum problem. By fixing one number and using two pointers for the remaining two numbers, we can find all valid triplets efficiently.

Main Ideas:

  1. Sort the array to enable two-pointer technique and easy duplicate handling
  2. Fix one element (index i) and find two other elements that sum to -nums[i]
  3. Use two pointers on the remaining array to find pairs
  4. Skip duplicates to avoid duplicate triplets in the result

Pattern Recognition

This is a Two Pointers pattern combined with:

  • Sorting for optimization
  • Nested iteration (outer loop + two pointers)
  • Duplicate handling
  • Target sum variation (3 numbers instead of 2)

Approach

  1. Sort the Array: Sort nums in ascending order
  2. Outer Loop: Iterate through array with index i
    • Skip if nums[i] > 0 (no way to get sum = 0)
    • Skip duplicates for i to avoid duplicate triplets
  3. Two Pointers: For each i, use two pointers:
    • left = i + 1, right = length - 1
    • Calculate sum = nums[i] + nums[left] + nums[right]
    • If sum == 0: Add triplet, skip duplicates for left and right
    • If sum < 0: Move left++
    • If sum > 0: Move right--
  4. Return Result: All unique triplets found

Edge Cases

  • Array with less than 3 elements
  • All positive or all negative numbers
  • Multiple zeros
  • Duplicate numbers requiring careful handling
  • Empty result

Complexity Analysis

  • Time Complexity: O(n²) where n is the length of the array
    • Sorting: O(n log n)
    • Outer loop: O(n)
    • Inner two pointers: O(n)
    • Total: O(n log n + n²) = O(n²)
  • Space Complexity: O(1) or O(n)
    • O(1) if we don't count the output array
    • O(n) for sorting (depending on sort implementation)

Solution

java
1class Solution {
2    public List<List<Integer>> threeSum(int[] nums) {
3        List<List<Integer>> result = new ArrayList<>();
4
5        // Sort array to enable two-pointer technique
6        Arrays.sort(nums);
7
8        // Iterate through array, fixing first element
9        for (int i = 0; i < nums.length - 2; i++) {
10            // Skip positive numbers (can't sum to 0)
11            if (nums[i] > 0) break;
12
13            // Skip duplicates for first element
14            if (i > 0 && nums[i] == nums[i - 1]) continue;
15
16            // Two pointers for remaining elements
17            int left = i + 1;
18            int right = nums.length - 1;
19
20            while (left < right) {
21                int sum = nums[i] + nums[left] + nums[right];
22
23                if (sum == 0) {
24                    // Found a triplet
25                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
26
27                    // Skip duplicates for left pointer
28                    while (left < right && nums[left] == nums[left + 1]) {
29                        left++;
30                    }
31
32                    // Skip duplicates for right pointer
33                    while (left < right && nums[right] == nums[right - 1]) {
34                        right--;
35                    }
36
37                    // Move both pointers
38                    left++;
39                    right--;
40                } else if (sum < 0) {
41                    // Sum too small, need larger number
42                    left++;
43                } else {
44                    // Sum too large, need smaller number
45                    right--;
46                }
47            }
48        }
49
50        return result;
51    }
52}
53
Loading visualizer...