ToolMight LogoToolMight
MediumTwo PointersArrays & HashingPattern: Sort then Two PointersPattern: Duplicate SkippingPattern: Triplet Zero Sum

3Sum

Find all unique triplets in an array that sum up to zero. The premier problem for learning how to combine sorting with two-pointer inward scans to avoid cubic brute force.

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 & Constraints

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. 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.
Constraints
  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Sort & Two-Pointer Inward Scan

Optimal Approach
Time:O(n²)
Space:O(1) to O(n)

Sort the array first. Fix the first element with an outer loop, then use two converging pointers to find pairs that sum to the target negation in O(n²) time.

Time ComplexityO(n²)

Sorting takes O(n log n). The outer loop runs N times, and each two-pointer inner scan takes O(n). Total runtime is O(n log n + n²) = O(n²).

Space ComplexityO(1) to O(n)

O(1) auxiliary space beyond the output array if in-place sorting is used, or O(n) for the sorting stack frames depending on language implementation.

Underlying algorithmic logic

Why Naive Brute Force Is Prohibitive

An exhaustive three-loop search evaluates all combinations in O(n³) time. For N = 3,000, 3000³ is 27,000,000,000 operations, which guarantees a timeout.

The Two-Pointer Reduction

If we sort the array first (O(n log n)), we can reduce the 3-variable problem into a sequence of sorted 2-variable problems:

  1. Sort `nums` in ascending order.
  2. Iterate i from 0 to n - 3:
  • Pruning: If nums[i] > 0, terminate the outer loop immediately! Since the array is sorted, any subsequent positive numbers can never sum to zero.
  • Skip Outer Duplicates: If i > 0 and nums[i] == nums[i - 1], skip to prevent duplicate triplets.
  • Set left = i + 1 and right = n - 1.
  1. While left < right:
  • Calculate sum = nums[i] + nums[left] + nums[right].
  • If `sum == 0`: We found a valid triplet! Record [nums[i], nums[left], nums[right]].
  • Advance left++ while skipping any identical consecutive values (nums[left] == nums[left - 1]).
  • Decrement right-- while skipping any identical consecutive values (nums[right] == nums[right + 1]).
  • If `sum < 0`: The sum is too small. Advance left++ to increase value.
  • If `sum > 0`: The sum is too large. Decrement right-- to decrease value.

Handling Duplicates Without Extra Sets

The genius of sorting first is that duplicate numbers are clustered together. By explicitly skipping identical numbers at both the outer pivot i and the inner pointers (left and right), we guarantee zero duplicate triplets without wasting memory on an auxiliary hash set.

Step-by-step execution walkthrough

1
Sort Array

[-1, 0, 1, 2, -1, -4] sorted becomes [-4, -1, -1, 0, 1, 2].

nums = [-4, -1, -1, 0, 1, 2]
2
Outer Pivot at i = 0 (val: -4)

Pointers at left = 1 (-1), right = 5 (2). Maximum possible sum is -4 + 1 + 2 = -1 < 0. No pair can reach 0 with -4.

left sweeps to right without finding sum == 0
3
Outer Pivot at i = 1 (val: -1)

left = 2 (-1), right = 5 (2). Sum: (-1) + (-1) + 2 = 0! Triplet [-1, -1, 2] recorded.

Found [-1, -1, 2]. Advance left and decrement right.
4
Inner Scan Continues

left = 3 (0), right = 4 (1). Sum: (-1) + 0 + 1 = 0! Triplet [-1, 0, 1] recorded.

Found [-1, 0, 1]
Advantages
  • •Optimal O(n²) runtime
  • •Zero memory waste by skipping duplicate values in-place
Trade-offs
  • •Mutates original array ordering (requires sorting)

Code Implementations

Copy & paste production-ready solutions for Sort & Two-Pointer Inward Scan in your language of choice

File: solution.py
Python
def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    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:
                res.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 res
if __name__ == "__main__":
    nums = [-1, 0, 1, 2, -1, -4]
    print("Unique Triplets:", three_sum(nums))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyTwo Pointers
Visualizer

Valid Palindrome

Determine if a string is a palindrome considering only alphanumeric characters and ignoring case. The canonical problem for learning the two-pointer inward convergence technique.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

2 approaches(O(n))
Learn logic