Find All Triplets With Given Sum: Three Approaches

The three-sum problem asks for every triplet in an array whose elements add up to a target value. Three standard methods solve it in interview settings, and they trade off readability, time complexity, and extra space.

This article covers all three: the brute-force O(n^3) baseline, the sort-then-two-pointer O(n^2) optimisation, and the hashing variant. Each is shown with Python code, a complexity note, and the situation where it wins. The end of the article walks through a single worked input from start to finish so the two-pointer logic is unambiguous.

The Problem at a Glance

You are given an integer array arr of size n and a target integer sum_value. Return every triplet (arr[i], arr[j], arr[k]) such that i < j < k and arr[i] + arr[j] + arr[k] == sum_value.

The standard worked input from the legacy FACE Prep version of this problem:

• Input: arr = [0, -1, 2, -3, 1], target sum_value = -2
• Output: two triplets — {0, -3, 1} and {-1, 2, -3} (in any order)

Both triplets sum to -2. Verify: 0 + (-3) + 1 = -2, and (-1) + 2 + (-3) = -2. The other eight C(5, 3) candidate triplets all sum to something other than -2.

A few constraints worth pinning down before writing code, because they change which method is appropriate:

• Distinct triplets vs. distinct index sets. Most interview variants want distinct value-triplets — {1, 2, 3} counted once even if the value 2 appears twice in the input. The two-pointer method handles this cleanly with a skip-duplicates pass; the hash and brute methods need a post-filter or a set of sorted tuples.
• Negative numbers and zero are allowed. The example shows this. Any algorithm that assumes positive values will fail.
• The triplet may include duplicates from the input. If arr = [1, 1, 2] and target = 4, then (1, 1, 2) is a valid triplet because both 1s come from different indices.
• Output order is unspecified. Most graders accept any order, both within a triplet and across triplets.

Method 1: Three Nested Loops (Brute Force)

The mechanical translation of the problem statement. Three loops, check the sum, print on a hit.

def find_triplets_brute(arr, sum_value):
    n = len(arr)
    triplets = []
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if arr[i] + arr[j] + arr[k] == sum_value:
                    triplets.append((arr[i], arr[j], arr[k]))
    return triplets

• Time: O(n^3) — three nested scans.
• Space: O(1) extra (excluding the output list).
• When to use it: when n is small (< 100), when interview clarity matters more than complexity, or when you want a reference implementation to validate the optimised versions against.

The brute force is genuinely worth writing once before reaching for the optimisations. It anchors what “all triplets” actually means and gives you something to diff against when the two-pointer code returns the wrong count.

Method 2: Sort, Then Two Pointers

Sorting the array first lets you replace the inner two loops with a single linear sweep. The idea: fix the leftmost element with the outer loop. The remaining two elements must sum to sum_value - arr[i], which is a two-sum problem on a sorted subarray. Two pointers (one at the start of the subarray, one at the end) solve two-sum in O(n).

The full algorithm:

• Sort arr in ascending order. O(n log n).
• For each index i from 0 to n - 3:
  • Set p = i + 1 and q = n - 1.
  • While p < q:
    • Compute s = arr[i] + arr[p] + arr[q].
    • If s == sum_value, record the triplet, then increment p and decrement q.
    • If s < sum_value, increment p (need a larger sum).
    • If s > sum_value, decrement q (need a smaller sum).

def find_triplets_two_pointer(arr, sum_value):
    arr_sorted = sorted(arr)
    n = len(arr_sorted)
    triplets = []
    for i in range(n - 2):
        p, q = i + 1, n - 1
        while p < q:
            s = arr_sorted[i] + arr_sorted[p] + arr_sorted[q]
            if s == sum_value:
                triplets.append((arr_sorted[i], arr_sorted[p], arr_sorted[q]))
                p += 1
                q -= 1
            elif s < sum_value:
                p += 1
            else:
                q -= 1
    return triplets

• Time: O(n^2) — outer loop is O(n), inner two-pointer scan is O(n).
• Space: O(n) for sorted() (Python’s sorted returns a new list); O(1) if you sort in place with arr.sort().

The two-pointer pattern is the same one used in many sort-and-scan problems. Compare with the sort-then-scan pattern used in the Noddy max-gap problem. The structure is recognisable across the family. For the deduplication-aware production version, see the LeetCode 3Sum reference solutions.

To skip duplicate triplets, add three checks:

• After incrementing p, keep incrementing while arr_sorted[p] == arr_sorted[p - 1].
• After decrementing q, keep decrementing while arr_sorted[q] == arr_sorted[q + 1].
• At the top of the outer loop, skip i when arr_sorted[i] == arr_sorted[i - 1] and i > 0.

Method 3: Hashing in the Inner Loop

Hashing replaces the inner two-pointer scan with a hash-set lookup. For each pair (i, j), compute the value the third element must take: target_third = sum_value - arr[i] - arr[j]. If that value has already been seen during the inner scan, you have a triplet.

The algorithm:

• For i from 0 to n - 2:
  • Create an empty hash set seen.
  • For j from i + 1 to n - 1:
    • Compute target_third = sum_value - arr[i] - arr[j].
    • If target_third is in seen, record the triplet (arr[i], target_third, arr[j]).
    • Insert arr[j] into seen.

def find_triplets_hashing(arr, sum_value):
    n = len(arr)
    triplets = []
    for i in range(n - 1):
        seen = set()
        for j in range(i + 1, n):
            target_third = sum_value - arr[i] - arr[j]
            if target_third in seen:
                triplets.append((arr[i], target_third, arr[j]))
            seen.add(arr[j])
    return triplets

• Time: O(n^2) average — the hash insert and lookup are O(1) average.
• Space: O(n) for the hash set, reset per outer iteration.
• When to use it: when you cannot afford to sort (the input order matters for downstream code), when you want a single-pass streaming feel, or when the values are not directly comparable.

Hashing also has a worst-case O(n) per lookup if the hash function degenerates, but for ordinary integer keys in Python’s set, this almost never happens in practice.

Worked Example: Two-Pointer Trace Step by Step

Input: arr = [0, -1, 2, -3, 1], target sum_value = -2.

After sorting: arr_sorted = [-3, -1, 0, 1, 2]. Indices 0..4.

The trace, with each (i, p, q) step and the running sum:

• i = 0 — fix arr_sorted[0] = -3. Start with p = 1, q = 4.
  • p=1, q=4 — sum = -3 + (-1) + 2 = -2. Match. Record (-3, -1, 2). Move p = 2, q = 3.
  • p=2, q=3 — sum = -3 + 0 + 1 = -2. Match. Record (-3, 0, 1). Move p = 3, q = 2.
  • p is no longer less than q. Exit inner loop.
• i = 1 — fix arr_sorted[1] = -1. Start with p = 2, q = 4.
  • p=2, q=4 — sum = -1 + 0 + 2 = 1. Greater than -2. Decrement q = 3.
  • p=2, q=3 — sum = -1 + 0 + 1 = 0. Greater than -2. Decrement q = 2.
  • p is no longer less than q. Exit.
• i = 2 — fix arr_sorted[2] = 0. Start with p = 3, q = 4.
  • p=3, q=4 — sum = 0 + 1 + 2 = 3. Greater than -2. Decrement q = 3.
  • Exit.
• i = 3 — outer loop ends (n - 2 = 3 is the last allowed i, but p = 4 and q = 4 mean the inner loop never runs).

Output: [(-3, -1, 2), (-3, 0, 1)].

Re-stated in the original input’s value form: the triplets are {-1, 2, -3} and {0, -3, 1}. Both match the expected output.

Choosing Between the Three Methods

Method	Time	Extra Space	Preserves Input Order	Duplicate Handling
Three nested loops	O(n^3)	O(1)	Yes	Manual post-filter
Sort + two pointers	O(n^2)	O(1) in-place sort, O(n) otherwise	No	Built-in skip pattern
Hashing in inner loop	O(n^2) avg	O(n)	Yes	Manual post-filter

Default to the two-pointer method for placement interviews. It is the canonical answer to LeetCode-style 3Sum questions and the duplicate-handling story is the cleanest. Switch to hashing only when the original index order matters or when sorting is genuinely off-limits. Switch to brute force only when the array is tiny and the interviewer is asking you to talk through correctness before optimisation.

The same decision tree shows up across DSA problems where greedy is tempting but a structured method is correct. The DP-style problems where the greedy approach fails are a parallel case in which the right method beats the obvious one. For lighter warmup, the pattern-printing warmup problems build the loop discipline that makes the inner two-pointer mechanics second nature.

Where DSA Meets AI Engineering

The three-sum problem is small enough to fit on a whiteboard, but the same shape (fix one element, search the rest with a faster method) recurs in production AI code: post-filtering nearest-neighbour results, narrowing a candidate set before a re-ranker, finding embedding triplets that satisfy a margin constraint. The placement interview tests whether you can write the O(n^2) version without bugs. The production setting tests whether you reach for it when you need it.

If the gap from “I can solve 3Sum on LeetCode” to “I can spot the same shape in a real codebase” is the one you want to close, TinkerLLM is the low-risk first step at ₹299. It is a self-paced playground for building small things with language models. The projects it nudges you toward use exactly this kind of inner-loop reasoning when you start optimising retrieval, and the two-pointer trace above is the same step-through you do when an embedding lookup is too slow and you need to find the slow line.