Three Sum

The Problem

Given an integer array arr, find all unique triplets [a, b, c] such that a + b + c = 0. The solution set must not contain duplicate triplets.

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

Examples

Example 1

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

Example 2

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

Example 3

Input:  arr = [1, 2, 3]
Output: []
Explanation: No triplet sums to 0.

Example 4

Input:  arr = [-2, 0, 0, 2, 2]
Output: [[-2, 0, 2]]

Intuition: Fix One, Two-Pointer the Rest

Three Sum extends Two Sum with one extra element fixed. If we pick one element arr[i] and fix it, the problem reduces to:

Find all pairs in the remaining subarray that sum to −arr[i].

That’s exactly Duplicate Aware Two Sum! And we know how to solve that in O(n) with two pointers on a sorted array.

So the full algorithm is:

1. Sort the array
2. Fix each element arr[i] with an outer loop
3. Two-pointer on arr[i+1..n-1] searching for pairs summing to −arr[i]
4. Skip duplicates at every level to avoid repeated triplets

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr"]
  Outer["for i in 0 → n-3\n(fix arr[i])"]
  SkipI{"arr[i] == arr[i-1]?\n(duplicate outer)"}
  SetTP["left = i+1,  right = n-1\ntarget = -arr[i]"]
  InLoop{"left < right?"}
  Calc["total = arr[left] + arr[right]"]
  Found{"total == target?"}
  Record["append [arr[i], arr[left], arr[right]]\nskip left & right duplicates\nleft++,  right--"]
  Less["left++"]
  Greater["right--"]
  CanBreak{"arr[i] > 0?"}
  Break["break  (sorted: all future sums > 0)"]

  Sort --> Outer --> CanBreak
  CanBreak -->|"yes"| Break
  CanBreak -->|"no"| SkipI
  SkipI -->|"yes, skip"| Outer
  SkipI -->|"no"| SetTP --> InLoop
  InLoop -->|"yes"| Calc --> Found
  Found -->|"yes"| Record --> InLoop
  Found -->|"no, <"| Less --> InLoop
  Found -->|"no, >"| Greater --> InLoop
  InLoop -->|"no"| Outer

Three Sum — outer loop fixes one element; inner two-pointer finds all valid pairs summing to the negative of that element.

Applying the Diagnostic Questions

Three Sum sits at the intersection of two patterns you’ve already seen — the subproblem pattern from this section and the reduction technique from the previous one. The diagnostic questions make this explicit.

Q1 — Why “fix one element and reduce to a pair-finding subproblem”?

Mental model: Think of the problem as searching through all triples (a, b, c) where a + b + c = 0. That’s a three-dimensional search. If you lock one dimension — say a = arr[i] — you’re left with a two-dimensional search: b + c = −arr[i]. Two unknowns on a sorted array is a problem you already know how to solve in O(n).

Concrete numbers: take arr = [-4, -1, -1, 0, 1, 2] (sorted). Fix arr[1] = -1. Now target = −(−1) = 1. The subproblem is: find all pairs in [-1, 0, 1, 2] summing to 1. Two pointers find (-1, 2) and (0, 1) — giving triplets [-1, -1, 2] and [-1, 0, 1].

What breaks without this decomposition? Without fixing one element, you’d need three nested loops to check every triple — O(n³). Fixing one element collapses the search from three dimensions to two, giving O(n²). The outer loop runs at most n times; the inner two-pointer pass runs in O(n) per iteration.

Q2 — Why “the inner subproblem is Duplicate Aware Two Sum, solved with two pointers”?

Mental model: Once you fix arr[i] and have a sorted subarray with a target, the problem is identical to the Two Sum problems in the previous section. The subarray is already sorted (sorting once before the outer loop covers all inner passes). arr[left] is always the minimum remaining value and arr[right] is always the maximum. Every pointer move has a predictable, guaranteed effect: moving left right always increases the sum; moving right left always decreases it.

Concrete numbers: subarray [-1, 0, 1, 2], target 1:

• left=0 (-1), right=3 (2): sum = 1 — match ✓, record and move both inward
• left=1 (0), right=2 (1): sum = 1 — match ✓, record and move both inward
• left=2, right=1: left ≥ right — done

Two pointer moves, two results, O(n) total. A three-nested-loop brute force would take 6 comparisons for the same 4-element window.

What breaks if you skip sorting? Without sorting the subarray, moving left right no longer guarantees a larger value — you might skip the correct pair entirely. The decisive-direction property that makes two pointers work comes entirely from the sorted order.

Pattern note: Three Sum is a two-pointer subproblem problem at the outer level (decompose by fixing one element), and a two-pointer reduction problem at the inner level (sort + two-pointer on the subarray). The nesting of patterns is what makes it an O(n²) solution — one layer of decomposition, one layer of linear two-pointer inside.

The Early-Exit Optimisation

Since the array is sorted, if arr[i] > 0, then arr[left] ≥ arr[i] > 0 and arr[right] ≥ arr[i] > 0 — the sum of any three elements from position i onward is positive. No triplet can sum to 0. Break early.

Solution

from typing import List

class Solution:
    def three_sum(self, arr: List[int]) -> List[List[int]]:
        # Sort the array to enable the two-pointer subproblem approach
        arr.sort()
        n      = len(arr)
        result = []

        for i in range(n - 2):
            # Early exit: if arr[i] > 0, all elements from i onward are positive — no triplet sums to 0
            if arr[i] > 0:
                break

            # Skip duplicate values for the fixed element to avoid duplicate triplets
            if i > 0 and arr[i] == arr[i - 1]:
                continue

            # Set up the two-pointer subproblem: find pairs in arr[i+1..n-1] summing to -arr[i]
            left, right = i + 1, n - 1
            target = -arr[i]

            # Run the two-pointer pass on the remaining subarray
            while left < right:
                total = arr[left] + arr[right]

                if total == target:
                    result.append([arr[i], arr[left], arr[right]])

                    # Skip consecutive left duplicates to avoid duplicate triplets
                    while left < right and arr[left] == arr[left + 1]:
                        left += 1
                    # Skip consecutive right duplicates to avoid duplicate triplets
                    while left < right and arr[right] == arr[right - 1]:
                        right -= 1

                    # Move both pointers inward after recording the match
                    left  += 1
                    right -= 1

                elif total < target:
                    # Sum too small — move left pointer to a larger value
                    left += 1
                else:
                    # Sum too large — move right pointer to a smaller value
                    right -= 1

        return result


# --- Test ---
sol = Solution()
print(sol.three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
print(sol.three_sum([0, 0, 0, 0]))            # [[0,0,0]]
print(sol.three_sum([1, 2, 3]))               # []
print(sol.three_sum([-2, 0, 0, 2, 2]))        # [[-2,0,2]]

Dry Run — Example 1

arr = [-1, 0, 1, 2, -1, -4] → sorted: [-4, -1, -1, 0, 1, 2]

i=0, arr[i]=-4, target=4, left=1, right=5:

No triplets for i=0.

i=1, arr[i]=-1, target=1, left=2, right=5:

i=2, arr[i]=-1: duplicate of arr[1] → skip

i=3, arr[i]=0: arr[i] > 0? No. target=0, left=4, right=5:

i=4: only 1 element left — loop ends.

Result: [[-1,-1,2], [-1,0,1]] ✓

Complexity Analysis

Edge Cases

Key Takeaway

Three Sum = outer fixed element + inner Duplicate Aware Two Sum. The reduction insight: fix one element and reduce to a two-variable sum problem on the sorted remainder. The same duplicate-skipping logic from the two-pointer reduction section applies — now at two levels (the fixed element and both inner pointers). The time complexity is O(n²), which is optimal for this problem.