Zero-Sum Triplet Finder

You are twenty minutes into a Google phone screen and the interviewer says: "Given an array of integers, find all unique triplets that sum to zero." If you have spent any time on interview prep, you recognize this instantly. It is 3Sum, one of the most frequently asked problems across Google, Meta, Amazon, Uber, and Yahoo. On Firecode.io it appears as "Zero-Sum Triplet Finder," but it is the same classic problem also known as 3Sum on other platforms. Getting this right in an interview signals that you understand sorting, two pointers, and duplicate handling, three skills that transfer directly to harder problems.

TL;DR

Sort the array, then iterate with an outer loop. For each element, use two pointers (one at the start and one at the end of the remaining subarray) to find pairs that sum to the negative of the fixed element. Skip duplicates at all three levels: the outer element, the left pointer, and the right pointer. This runs in O(n^2) time and O(n) space.

Why This Problem Matters

3Sum is where sorting meets two pointers. It builds directly on Two Sum but adds a layer of complexity: you need to handle three elements instead of two, and the result must contain no duplicate triplets. The problem tests whether you can decompose a harder problem into a known subproblem (Two Sum on a sorted array) and whether you can manage duplicates without resorting to a hash set. These are patterns you will reuse in 4Sum, 3Sum Closest, and any problem that asks for unique combinations.

Understanding the Problem

Given: An array of integers nums

Find: All unique triplets [nums[i], nums[j], nums[k]] where i != j != k and nums[i] + nums[j] + nums[k] == 0

Return: A list of triplets with no duplicates

Here is the example input:

With threeSum([-1, 0, 1, 2, -1, -4]), the expected output is [[-1, -1, 2], [-1, 0, 1]].

Constraints

• Array length is between 3 and 6,000
• Values range from -100,000 to 100,000
• No duplicate triplets in the output
• Target O(n^2) time complexity

The Brute Force Trap

The naive approach checks every possible triplet with three nested loops. That is O(n^3), which for an array of 6,000 elements means 36 billion operations. For an interviewer, hearing "three nested loops" is a red flag. They want to see you recognize that sorting unlocks a better approach.

Solution Approach: Sort + Two Pointers

Sorting the array is the first move. Once sorted, you can fix one element and use two pointers on the remaining subarray to find pairs that complete the triplet. This reduces the problem from O(n^3) to O(n^2).

After sorting [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2].

Here is the strategy:

1. Sort the array
2. For each element nums[i], set left = i + 1 and right = n - 1
3. Calculate sum = nums[i] + nums[left] + nums[right]
4. If sum == 0, record the triplet. Skip duplicates, then move both pointers inward.
5. If sum < 0, move left right to increase the sum
6. If sum > 0, move right left to decrease the sum
7. Skip duplicate values of nums[i] in the outer loop

The two-pointer technique works because sorting creates a monotonic structure. Moving left right always increases the partial sum, and moving right left always decreases it.

Prefer a different language? Jump to solutions in other languages.

Step-by-Step Walkthrough

Let's trace through [-4, -1, -1, 0, 1, 2] (already sorted).

Iteration 1: Fix i=0, nums[i]=-4

We need two numbers that sum to 4 from the remaining subarray. The largest possible sum from [-1, -1, 0, 1, 2] is 1 + 2 = 3, which is less than 4. No triplet exists with -4.

Iteration 2: Fix i=1, nums[i]=-1

We need two numbers that sum to 1. Left starts at index 2, right at index 5.

Two triplets found: [-1, -1, 2] and [-1, 0, 1].

Iterations 3-4: Remaining elements

Index 2 has value -1, same as index 1, so the duplicate check skips it. Index 3 has value 0, but no pair in [1, 2] sums to 0. The algorithm finishes with [[-1, -1, 2], [-1, 0, 1]].

Implementation

import java.util.*;

public class Solution {
  public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
      return result;
    }

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
      // Skip duplicate values for the outer element
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }

      int left = i + 1;
      int 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]));
          // Skip duplicates for left pointer
          while (left < right && nums[left] == nums[left + 1]) {
            left++;
          }
          // Skip duplicates for right pointer
          while (left < right && nums[right] == nums[right - 1]) {
            right--;
          }
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else {
          right--;
        }
      }
    }

    return result;
  }
}

The outer loop fixes one element, then the inner while loop runs the two-pointer scan. After finding a valid triplet, we skip past duplicate values on both sides before advancing the pointers. This ensures every triplet in the output is unique.

Handling Duplicates

Duplicate avoidance is the trickiest part of 3Sum and the most common source of bugs. There are three levels of deduplication, all of which are necessary.

Level 1 (outer loop): If nums[i] == nums[i - 1], the entire two-pointer scan for this value has already been done. Skip it.

Level 2 (left pointer): After finding a triplet, advance left past any consecutive equal values before the main left++. Otherwise the same left value could produce the same triplet with a different right value that we have already recorded.

Level 3 (right pointer): Same logic in reverse. Retreat right past consecutive equal values before the main right--.

Missing any of these three checks will produce duplicate triplets in the output.

Complexity Analysis

Time Complexity: O(n^2)

Sorting costs O(n log n). The outer loop runs at most n times, and each two-pointer scan is O(n). The dominant term is the nested O(n) scan inside the O(n) loop, giving O(n^2). The sorting cost is absorbed.

Space Complexity: O(n)

The result list can hold up to O(n^2 / 3) triplets in the worst case, but the auxiliary space (beyond the output) is O(log n) for the sort. If we count the output, space is O(n) in typical interview analysis. The two-pointer scan itself uses O(1) extra space.

Why Not Use a Hash Set?

You could avoid sorting and use a hash set to check for the third element. This also runs in O(n^2) but makes duplicate elimination harder: you need to normalize each triplet (sort the three values) and check against a set of seen triplets. The sort-and-two-pointer approach handles duplicates more cleanly through the three skip checks.

Edge Cases Worth Testing

All Zeros

[0, 0, 0] produces [[0, 0, 0]]. The duplicate-skipping logic ensures only one copy appears.

No Valid Triplet

[0, 1, 1] produces an empty list. The only possible sum is 0 + 1 + 1 = 2, which is not zero.

All Positive or All Negative

If every element is positive, no three of them can sum to zero (the minimum sum is already positive). Same logic for all negative. The algorithm handles this naturally since the two-pointer scan will never find a sum of zero.

Fewer Than Three Elements

With fewer than three elements, no triplet is possible. The guard clause at the top returns an empty list immediately.

Common Pitfalls

1. Forgetting to sort first: The two-pointer approach requires a sorted array. Without sorting, moving left and right has no predictable effect on the sum.

2. Only deduplicating at one level: Skipping only the outer loop duplicates is not enough. You also need to skip inner duplicates after finding a match, or the same triplet will appear multiple times.

3. Off-by-one in duplicate skipping: The outer check is nums[i] == nums[i - 1], not nums[i] == nums[i + 1]. Checking forward would skip the first occurrence of a value, potentially missing valid triplets.

4. Not moving both pointers after a match: After recording a triplet and skipping duplicates, you must increment left and decrement right. Forgetting either one causes an infinite loop.

Interview Tips

When solving 3Sum in an interview:

1. Start with brute force: "Three nested loops give O(n^3). We can do better by sorting and using two pointers." This shows you understand the baseline.

2. Explain the reduction: "Fixing one element reduces 3Sum to Two Sum on a sorted array. That is the core insight." Interviewers want to see you decompose the problem.

3. Draw the pointer movement: Sketch a sorted array, place L and R, and show how they converge. This makes the algorithm concrete.

4. Address duplicates proactively: "There are three levels of duplicate skipping." Mention this before the interviewer asks. It shows you have thought through the tricky parts.

5. Discuss follow-ups: "This extends to 4Sum by adding another outer loop. 3Sum Closest changes the target from zero to the nearest sum." Showing awareness of the problem family demonstrates depth.

Key Takeaways

• Sorting the array is the prerequisite that makes two pointers work. Without a sorted array, you cannot reason about the direction to move pointers.
• The problem decomposes into n instances of Two Sum on a sorted array, giving O(n^2) total.
• Duplicate handling requires three separate checks: the outer element, the left pointer, and the right pointer.
• The sort-and-two-pointer pattern transfers directly to 4Sum, 3Sum Closest, and other k-Sum variants.
• In interviews, explain the reduction from 3Sum to Two Sum early. It demonstrates structured thinking and sets up the algorithm clearly.

Related Problems

Once you are comfortable with 3Sum, try these problems that build on the same techniques:

• Two Sum - The simpler version where you find a pair instead of a triplet
• Find Pair Indices in Sorted Array - Two Sum on a sorted array, the exact subproblem that 3Sum reduces to
• Combining Overlapping Ranges - Another problem where sorting unlocks an efficient left-to-right scan

These problems and hundreds more are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Whether you are targeting Google, Meta, or Amazon, fluency with the sort-and-two-pointer pattern gives you a reliable technique for an entire family of interview problems.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def three_sum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        n = len(nums)

        for i in range(n - 2):
            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:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1

        return result

Python's sort() is Timsort, giving O(n log n). The range(n - 2) stops the outer loop at the right place since we need at least two elements after i.

JavaScript

class Solution {
  threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
      if (i > 0 && nums[i] === nums[i - 1]) continue;

      let left = i + 1;
      let right = nums.length - 1;

      while (left < right) {
        const sum = nums[i] + nums[left] + nums[right];

        if (sum === 0) {
          result.push([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else {
          right--;
        }
      }
    }

    return result;
  }
}

The custom comparator (a, b) => a - b is critical. JavaScript's default sort() converts elements to strings, which would sort [-1, 0, 1, 2] incorrectly.

TypeScript

class Solution {
  threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const result: number[][] = [];

    for (let i = 0; i < nums.length - 2; i++) {
      if (i > 0 && nums[i] === nums[i - 1]) continue;

      let left = i + 1;
      let right = nums.length - 1;

      while (left < right) {
        const sum = nums[i] + nums[left] + nums[right];

        if (sum === 0) {
          result.push([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else {
          right--;
        }
      }
    }

    return result;
  }
}

Identical to JavaScript with type annotations. The number[][] return type makes the nested list structure explicit.

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<std::vector<int>> threeSum(std::vector<int> &nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());

    for (size_t i = 0; i < nums.size(); ++i) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }

      int left = i + 1;
      int right = nums.size() - 1;

      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum == 0) {
          result.push_back({nums[i], nums[left], nums[right]});
          while (left < right && nums[left] == nums[left + 1]) {
            ++left;
          }
          while (left < right && nums[right] == nums[right - 1]) {
            --right;
          }
          ++left;
          --right;
        } else if (sum < 0) {
          ++left;
        } else {
          --right;
        }
      }
    }

    return result;
  }
};

C++ uses std::sort for O(n log n) sorting. The push_back with initializer list {nums[i], nums[left], nums[right]} creates the inner vector inline.

Go

package solution

import "sort"

func (s *Solution) ThreeSum(nums []int) [][]int {
    sort.Ints(nums)
    var result [][]int

    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                left++
                right--
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }

    return result
}

type Solution struct {}

Go uses sort.Ints for in-place integer sorting. The append function handles dynamic slice growth for the result.

Scala

class Solution {
  def threeSum(nums: Array[Int]): List[List[Int]] = {
    val sortedNums = nums.sorted
    val result = scala.collection.mutable.ListBuffer[List[Int]]()

    for (i <- 0 until sortedNums.length - 2) {
      if (i == 0 || (i > 0 && sortedNums(i) != sortedNums(i - 1))) {
        var low = i + 1
        var high = sortedNums.length - 1
        val sum = 0 - sortedNums(i)

        while (low < high) {
          if (sortedNums(low) + sortedNums(high) == sum) {
            result += List(sortedNums(i), sortedNums(low), sortedNums(high))
            while (low < high && sortedNums(low) == sortedNums(low + 1)) low += 1
            while (low < high && sortedNums(high) == sortedNums(high - 1)) high -= 1
            low += 1
            high -= 1
          } else if (sortedNums(low) + sortedNums(high) < sum) {
            low += 1
          } else {
            high -= 1
          }
        }
      }
    }

    result.toList
  }
}

Scala computes the target sum as 0 - sortedNums(i) and searches for pairs matching that target. The ListBuffer collects results mutably before converting to an immutable List.

Kotlin

class Solution {
  fun threeSum(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    if (nums.size < 3) {
      return result
    }

    nums.sort()

    for (i in 0 until nums.size - 2) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue
      }

      var left = i + 1
      var right = nums.size - 1

      while (left < right) {
        val sum = nums[i] + nums[left] + nums[right]
        if (sum == 0) {
          result.add(listOf(nums[i], nums[left], nums[right]))
          while (left < right && nums[left] == nums[left + 1]) {
            left++
          }
          while (left < right && nums[right] == nums[right - 1]) {
            right--
          }
          left++
          right--
        } else if (sum < 0) {
          left++
        } else {
          right--
        }
      }
    }

    return result
  }
}

Kotlin's listOf creates an immutable list for each triplet, while the outer mutableListOf allows appending.

Swift

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        if nums.count < 3 {
            return result
        }

        var nums = nums.sorted()

        for i in 0..<nums.count - 2 {
            if i > 0 && nums[i] == nums[i - 1] {
                continue
            }

            var left = i + 1
            var right = nums.count - 1

            while left < right {
                let sum = nums[i] + nums[left] + nums[right]
                if sum == 0 {
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right && nums[left] == nums[left + 1] {
                        left += 1
                    }
                    while left < right && nums[right] == nums[right - 1] {
                        right -= 1
                    }
                    left += 1
                    right -= 1
                } else if sum < 0 {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }

        return result
    }
}

Swift creates a sorted copy with nums.sorted() since the parameter is immutable. The var nums shadow lets us work with the sorted version.

Rust

impl Solution {
    pub fn three_sum(&self, mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        if nums.len() < 3 {
            return result;
        }

        nums.sort();

        for i in 0..nums.len() - 2 {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            let mut left = i + 1;
            let mut right = nums.len() - 1;

            while left < right {
                let sum = nums[i] + nums[left] + nums[right];
                if sum == 0 {
                    result.push(vec![nums[i], nums[left], nums[right]]);
                    while left < right && nums[left] == nums[left + 1] {
                        left += 1;
                    }
                    while left < right && nums[right] == nums[right - 1] {
                        right -= 1;
                    }
                    left += 1;
                    right -= 1;
                } else if sum < 0 {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }

        result
    }
}

The mut keyword on the parameter lets Rust sort the vector in place. The vec! macro creates each triplet as a new Vec<i32>.

C#

public class Solution {
    public List<List<int>> ThreeSum(int[] nums) {
        var result = new List<List<int>>();
        if (nums == null || nums.Length < 3) {
            return result;
        }

        Array.Sort(nums);

        for (int i = 0; i < nums.Length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.Length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.Add(new List<int> { nums[i], nums[left], nums[right] });
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }
}

C# uses Array.Sort for in-place sorting and collection initializer syntax new List<int> { ... } for each triplet.

Dart

class Solution {
  List<List<int>> threeSum(List<int> nums) {
    List<List<int>> result = [];
    if (nums.length < 3) {
      return result;
    }

    nums.sort();

    for (int i = 0; i < nums.length - 2; i++) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }

      int left = i + 1;
      int right = nums.length - 1;

      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum == 0) {
          result.add([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] == nums[left + 1]) {
            left++;
          }
          while (left < right && nums[right] == nums[right - 1]) {
            right--;
          }
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else {
          right--;
        }
      }
    }

    return result;
  }
}

Dart's sort() modifies the list in place. The list literal [nums[i], nums[left], nums[right]] creates each triplet inline.

PHP

<?php

class Solution {
    public function threeSum(array $nums): array {
        $result = [];
        if (count($nums) < 3) {
            return $result;
        }

        sort($nums);

        for ($i = 0; $i < count($nums) - 2; $i++) {
            if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
                continue;
            }

            $left = $i + 1;
            $right = count($nums) - 1;

            while ($left < $right) {
                $sum = $nums[$i] + $nums[$left] + $nums[$right];
                if ($sum === 0) {
                    $result[] = [$nums[$i], $nums[$left], $nums[$right]];
                    while ($left < $right && $nums[$left] === $nums[$left + 1]) {
                        $left++;
                    }
                    while ($left < $right && $nums[$right] === $nums[$right - 1]) {
                        $right--;
                    }
                    $left++;
                    $right--;
                } elseif ($sum < 0) {
                    $left++;
                } else {
                    $right--;
                }
            }
        }

        return $result;
    }
}

PHP uses strict comparison === to avoid type coercion issues. The $result[] shorthand appends to the array.

Ruby

class Solution
  def three_sum(nums)
    result = []
    if nums.nil? || nums.length < 3
      return result
    end

    nums.sort!

    (0...(nums.length - 2)).each do |i|
      next if i > 0 && nums[i] == nums[i - 1]

      left = i + 1
      right = nums.length - 1

      while left < right
        current_sum = nums[i] + nums[left] + nums[right]
        if current_sum == 0
          result << [nums[i], nums[left], nums[right]]
          left += 1 while left < right && nums[left] == nums[left + 1]
          right -= 1 while left < right && nums[right] == nums[right - 1]
          left += 1
          right -= 1
        elsif current_sum < 0
          left += 1
        else
          right -= 1
        end
      end
    end

    result
  end
end

Ruby's sort! modifies the array in place. The postfix while on the duplicate-skipping lines is idiomatic Ruby for single-statement loops.