DSA Series Day 7: 3Sum in Java, Python and Rust

Welcome to Day 7 of the Tekraze DSA series, where today’s problem is 3Sum, one of the most asked interview questions ever. Yesterday, in Day 7, Two Sum II, we found a pair that adds up to a target in a sorted array using two pointers. The nice part is that 3Sum is really that idea wrapped in a loop, plus one extra skill that trips up a lot of people: skipping duplicates.

Also Read: Two Sum : Find a Pair in a Sorted Array with Two Pointers

What is the 3Sum problem?

You get an integer array nums. Return every unique triplet [a, b, c] from three different positions where a + b + c = 0. The answer must not contain the same triplet twice, and the order of triplets does not matter.

text

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Input:  nums = [0, 1, 1]
Output: []

Input:  nums = [0, 0, 0]
Output: [[0, 0, 0]]

How should you think about 3Sum in plain words?

If you pick one number and lock it in place, the question becomes simple. You now need two other numbers that add up to minus that locked number. That is exactly a pair sum problem.

So the plan is short. Sort the array first, lock each number one at a time, and run the two pointer squeeze on everything to its right. Sorting also puts equal numbers next to each other, which makes skipping repeated triplets easy.

What does the brute force 3Sum solution look like?

Try every combination of three positions and store each matching triplet in sorted form inside a set so repeats disappear.

python

def three_sum_brute(nums):
    n = len(nums)
    found = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(t) for t in found]

Time is O(n³) because of the three nested loops. Space is up to O(n) for the set of results. With a few thousand numbers this already means billions of checks, so we need something smarter.

How do we get the optimal 3Sum solution?

Here is the whole method in six steps:

1. Sort the array.
2. Loop i over every index that still leaves room for two more numbers.
3. If nums[i] equals the number before it, skip it. We already found every triplet that starts with that value.
4. Set left = i + 1 and right to the last index.
5. If the sum is below zero, move left right. If it is above zero, move right left.
6. If the sum is zero, save the triplet, move both pointers, and keep moving them past equal values so the same triplet is not saved again.

There is also a small early exit. Once nums[i] is greater than zero, every number after it is also positive, so no triplet can add up to zero and we can stop.

Dry run on the classic input

Let us trace [-1, 0, 1, 2, -1, -4]. After sorting it becomes [-4, -1, -1, 0, 1, 2].

Locked number	What happens	Triplets saved
-4 (index 0)	Every pair sum stays negative, so left walks all the way to right	None
-1 (index 1)	left and right hit zero twice	[-1, -1, 2] and [-1, 0, 1]
-1 (index 2)	Same value as the one before, so it is skipped	None
0 (index 3)	Only pair left is 1 and 2, the sum is 3, so right moves and the loop ends	None

The output is [[-1, -1, 2], [-1, 0, 1]], which matches the expected answer.

3Sum time and space complexity

Time is O(n²). Sorting costs O(n log n), and then each locked number runs an O(n) squeeze. Space is O(1) extra beyond the output, or O(log n) to O(n) depending on the sort the language uses (Java’s Arrays.sort, Python’s sorted, Rust’s sort). If you want to see why O(n²) is a huge win over O(n³), our Big O helper post on time and space complexity explains it with charts.

3Sum Java solution

java

import java.util.*;
public class Solution {
    // Sort, fix one number, then run two pointers on the rest
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] tests = {{-1, 0, 1, 2, -1, -4}, {0, 1, 1}, {0, 0, 0, 0}, {-2, 0, 1, 1, 2}, {1, 2}};
        String[] expected = {"[[-1, -1, 2], [-1, 0, 1]]", "[]", "[[0, 0, 0]]", "[[-2, 0, 2], [-2, 1, 1]]", "[]"};
        for (int i = 0; i < tests.length; i++) {
            String got = threeSum(tests[i]).toString();
            System.out.println((got.equals(expected[i]) ? "PASS " : "FAIL ") + got);
        }
    }
}

Python solution

python

def three_sum(nums):
    # Sort, fix one number, then run two pointers on the rest
    nums = sorted(nums)
    result = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

if __name__ == "__main__":
    tests = [
        ([-1, 0, 1, 2, -1, -4], [[-1, -1, 2], [-1, 0, 1]]),
        ([0, 1, 1], []),
        ([0, 0, 0, 0], [[0, 0, 0]]),
        ([-2, 0, 1, 1, 2], [[-2, 0, 2], [-2, 1, 1]]),
        ([1, 2], []),
    ]
    for nums, expected in tests:
        got = three_sum(nums)
        print("PASS" if got == expected else "FAIL", got)

Rust solution

rust

// Sort, fix one number, then run two pointers on the rest
fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort();
    let n = nums.len();
    let mut result = Vec::new();
    for i in 0..n.saturating_sub(2) {
        if nums[i] > 0 {
            break;
        }
        if i > 0 && nums[i] == nums[i - 1] {
            continue;
        }
        let (mut left, mut right) = (i + 1, n - 1);
        while left < right {
            let sum = nums[i] + nums[left] + nums[right];
            if sum == 0 {
                result.push(vec![nums[i], nums[left], nums[right]]);
                left += 1;
                right -= 1;
                while left < right && nums[left] == nums[left - 1] {
                    left += 1;
                }
                while left < right && nums[right] == nums[right + 1] {
                    right -= 1;
                }
            } else if sum < 0 {
                left += 1;
            } else {
                right -= 1;
            }
        }
    }
    result
}

fn main() {
    let tests: Vec<(Vec<i32>, Vec<Vec<i32>>)> = vec![
        (vec![-1, 0, 1, 2, -1, -4], vec![vec![-1, -1, 2], vec![-1, 0, 1]]),
        (vec![0, 1, 1], vec![]),
        (vec![0, 0, 0, 0], vec![vec![0, 0, 0]]),
        (vec![-2, 0, 1, 1, 2], vec![vec![-2, 0, 2], vec![-2, 1, 1]]),
        (vec![1, 2], vec![]),
    ];
    for (nums, expected) in tests {
        let got = three_sum(nums);
        println!("{} {:?}", if got == expected { "PASS" } else { "FAIL" }, got);
    }
}

All three programs were run on the same five tests: the classic [-1, 0, 1, 2, -1, -4] case, an input with no answer, all zeros, a case with two triplets sharing the same first number, and an array too short to form a triplet. Every test passed in Java, Python and Rust. The Rust version uses saturating_sub so an array with fewer than three numbers does not underflow the loop range.

What are the 6 best tips and tricks for an easy 3Sum solution?

1. Spot the pattern. Whenever a problem asks for k numbers that hit a target, sort first and reduce it to the pair problem with two pointers.
2. Reuse Two Sum II. Think of 3Sum as a loop around yesterday’s solution with the target set to minus nums[i].
3. Skip duplicates in two places. Skip a repeated locked number at the top of the loop, and skip repeated left and right values right after you save a triplet.
4. Use the early break. If the locked number is positive, stop. It is a quick win that interviewers notice.
5. Test with zeros. Inputs like [0, 0, 0, 0] are the best check that your duplicate handling really works.
6. Talk about the next step. 4Sum adds one more outer loop on top of the same idea, giving O(n³).

What are the common mistakes people make?

• Forgetting to sort before using two pointers.
• Using a set of results to remove repeats instead of skipping them. It works, but it hides a weak understanding.
• Skipping duplicates of the locked number by comparing with nums[i + 1], which wrongly drops valid triplets like [-1, -1, 2].
• Moving only one pointer after finding a triplet, which can loop forever or save the same triplet again.
• Reading the result order too strictly, since any order of triplets is accepted.

Where is this pattern used in the real world?

You will mostly meet 3Sum itself in interviews, but the idea behind it, fixing one value and searching for pairs in the rest, shows up in real tools. Accounting software uses similar logic to find groups of transactions that cancel each other out during reconciliation. Shopping and recommendation systems look for bundles of items that fit a budget. Any time you need small groups that hit a target total, this sort plus squeeze trick is a good first step.

Which earlier posts in the series should you read?

Start with Day 1, Two Sum to see the pair sum idea with a hash map. Then read Day 6, Valid Palindrome, where two pointers begin, and Day 7, Two Sum, which is the exact building block for 3Sum. If you want a refresher on the structures behind these problems, our data structures cheat sheet covers them in Java, Python and Rust.

Frequently asked questions about 3Sum

What is the time complexity of 3Sum?

The sort plus two pointer solution runs in O(n²) time. Sorting takes O(n log n) and each locked number runs a linear squeeze. Brute force takes O(n³).

How do you avoid duplicate triplets?

Sort the array, skip a locked number that equals the one before it, and after saving a triplet move the left and right pointers past any equal values.

Why do we sort the array?

Sorting lets two pointers decide which way to move based on the sum. It also places equal numbers next to each other, which makes duplicate skipping simple.

Can 3Sum be solved with a hash map?

Yes. You can lock one number and use a hash set for the pair, which is also O(n²). Removing duplicate triplets gets messier, so two pointers is the cleaner interview answer.

How is 3Sum related to Two Sum II?

3Sum locks one number and solves Two Sum II on the rest of the sorted array with a target of minus that number.

Conclusion

3Sum is Two Sum II inside a loop, and the real skill is skipping duplicates. Solve it once on your own on LeetCode without looking at the code, then try the all zeros test. Next up in the series we keep going with two pointers on Container With Most Water.