What is the brute force approach and complexity for Triplet Sum in Array?

Three nested loops over i < j < k with time complexity O(N³) and space complexity O(1).

What is the optimal approach and complexity for Triplet Sum in Array?

Sort; fix arr[i]; move left/right inwards to find the pair with optimal time complexity O(N²) and space complexity O(1).

How do you identify the pattern for Triplet Sum in Array?

Look for key signals in the prompt: "three elements" indicates Three unknowns → fix one of them in a loop, leaving a pair problem.; "sum equal to target" indicates A pair with a known sum → Two Sum. In a sorted array that is opposite-ends two pointers.; "return true / false" indicates Order and positions don't matter for the answer → we are free to sort..

Triplet Sum in Array

Q: What is the optimal approach and complexity for Triplet Sum in Array?

Sort; fix arr[i]; move left/right inwards to find the pair with optimal time complexity O(N²) and space complexity O(1).

Q: How do you identify the pattern for Triplet Sum in Array?

Look for key signals in the prompt: "three elements" indicates Three unknowns → fix one of them in a loop, leaving a pair problem.; "sum equal to target" indicates A pair with a known sum → Two Sum. In a sorted array that is opposite-ends two pointers.; "return true / false" indicates Order and positions don't matter for the answer → we are free to sort..

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelTwo Pointers (fix one + opposite ends)

Complexity:O(N³)→O(N²)

Key Insight

Sort the array. Fix arr[i] as the smallest element of the triplet. In the part to its right, put left at the start and right at the end. If arr[left] + arr[right] is smaller than need, move left right to get a bigger sum. If it is bigger, move right left. If it equals need, we found a triplet.

Core Validity Invariant

For a fixed i, a pair (left, right) is the answer when arr[left] + arr[right] == need. Because the range is sorted, a sum that is too small means arr[left] is useless, and a sum that is too big means arr[right] is useless.

Problem

You are given an array of integers arr and a number target.

Can you pick three elements at three different positions whose sum is exactly target? Return true if such a triplet exists, otherwise false.

The same position can't be used twice, but two positions may hold the same value.

Input

An integer array arr of length n, and an integer target.

Output

true if some arr[i] + arr[j] + arr[k] == target with i, j, k all different, else false. (Function: bool hasTripletSum(vector<int>& arr, int target).)

Example 1

Input: arr = [1, 4, 45, 6, 10, 8], target = 13

Output: true

1 + 4 + 8 = 13.

Example 2

Input: arr = [1, 2, 4, 3, 6, 7], target = 10

Output: true

Several triplets work, for example 1 + 3 + 6 and 1 + 2 + 7. We only need to say that one exists.

Example 3

Input: arr = [40, 20, 10, 3, 6, 7], target = 24

Output: false

No three of these numbers add up to 24.

Constraints

• 3 ≤ n ≤ 10^3
• 1 ≤ arr[i] ≤ 10^5
• 1 ≤ target ≤ 3·10^5

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Does the order of the elements matter for the answer, or only which three I pick?
2.
If I already decided what the first number is, what is left to solve?
3.
Have I solved a "find two numbers with a given sum" problem before? What did it need?
4.
Would sorting the array change the answer? Would it make anything easier?
5.
Can I return as soon as I find one triplet, or do I need all of them?

Brute force approach

Idea

Check every group of three positions i < j < k. If any group adds up to target, return true. If none does, return false.

Thinking process

1
A triplet is just three different positions.
2
Using i < j < k makes sure each group is checked once and no position is reused.
3
Three loops, one sum check inside. Stop at the first match.

Code & Implementation

brute.cpp

class Solution {
public:
    bool hasTripletSum(vector<int>& arr, int target) {
        int n = arr.size();

        // Try every group of three different positions i < j < k.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] == target) return true;
                }
            }
        }
        return false;
    }
};

class Solution {
    public boolean hasTripletSum(int[] arr, int target) {
        int n = arr.length;

        // Try every group of three different positions i < j < k.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] == target) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

class Solution:
    def hasTripletSum(self, arr: list[int], target: int) -> bool:
        n = len(arr)

        # Try every group of three different positions i < j < k.
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if arr[i] + arr[j] + arr[k] == target:
                        return True

        return False

export function hasTripletSum(arr: number[], target: number): boolean {
    const n = arr.length;

    // Try every group of three different positions i < j < k.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] === target) return true;
            }
        }
    }
    return false;
}

Complexity

Time O(N³)Space O(1)

With n = 1000 there are about 1.7·10^8 triplets. That is too slow when the answer is false, because then every triplet must be checked.

Better approach

Why brute force is slow

For each pair (i, j) the brute force scans every k to look for one specific value: target − arr[i] − arr[j].

What repeated work are we doing?

Searching for a value by scanning is O(N). We do that search for every pair, so O(N²) searches × O(N) each.

What information can we reuse?

Remember the values we have already passed in a hash set. Then "is the value I need here?" is an O(1) lookup instead of a scan.

New approach

Idea

Fix the first element arr[i]. Now we need two elements after it that add up to need = target − arr[i]. Walk j to the right of i and keep a set of the values seen so far. If need − arr[j] is already in the set, we found the pair.

Thinking process

1
In the brute force, the inner two loops are just asking: is there a pair after i with sum need?
2
That is the classic Two Sum question, and Two Sum is solved with a hash set in one pass.
3
For each j, the partner it needs is need − arr[j]. If that value appeared earlier (between i and j), we are done.
4
A fresh set for each i keeps us from using arr[i] or anything before it by mistake.

Code & Implementation

better.cpp

class Solution {
public:
    bool hasTripletSum(vector<int>& arr, int target) {
        int n = arr.size();

        // Fix the first element. The other two must add up to target - arr[i].
        for (int i = 0; i < n; i++) {
            int need = target - arr[i];
            // Two Sum on arr[i+1 ..]: remember the values seen so far.
            unordered_set<int> seen;
            for (int j = i + 1; j < n; j++) {
                if (seen.count(need - arr[j])) return true;  // partner sits between i and j
                seen.insert(arr[j]);
            }
        }
        return false;
    }
};

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean hasTripletSum(int[] arr, int target) {
        int n = arr.length;

        // Fix the first element. The other two must add up to target - arr[i].
        for (int i = 0; i < n; i++) {
            int need = target - arr[i];
            // Two Sum on arr[i+1 ..]: remember the values seen so far.
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                if (seen.contains(need - arr[j])) {
                    return true; // partner sits between i and j
                }
                seen.add(arr[j]);
            }
        }
        return false;
    }
}

class Solution:
    def hasTripletSum(self, arr: list[int], target: int) -> bool:
        n = len(arr)

        # Fix the first element. The other two must add up to target - arr[i].
        for i in range(n):
            need = target - arr[i]
            # Two Sum on arr[i+1 ..]: remember the values seen so far.
            seen: set[int] = set()
            for j in range(i + 1, n):
                if need - arr[j] in seen:
                    return True  # partner sits between i and j
                seen.add(arr[j])

        return False

export function hasTripletSum(arr: number[], target: number): boolean {
    const n = arr.length;

    // Fix the first element. The other two must add up to target - arr[i].
    for (let i = 0; i < n; i++) {
        const need = target - arr[i];
        // Two Sum on arr[i+1 ..]: remember the values seen so far.
        const seen = new Set<number>();
        for (let j = i + 1; j < n; j++) {
            if (seen.has(need - arr[j])) return true; // partner sits between i and j
            seen.add(arr[j]);
        }
    }
    return false;
}

Complexity

Time O(N²)Space O(N)

Fast enough, but it builds a hash set of up to N values for every i. Sorting lets us do the same search with two pointers and no extra memory.

Optimized approach

Idea

Start from brute force

Brute force fixes i and j, then scans every k hoping to hit one exact value. For each i, the two inner loops try all O(N²) pairs to the right.

Find the repeated work

For a fixed i, most of those pairs are obviously hopeless. If the array is sorted and arr[j] + arr[last] is still too small, then arr[j] with any k is too small — but brute force checks them all anyway.

Define the state — what variables do I need?

i: The fixed element. It is the smallest value of the triplet we are looking for.
need: target − arr[i]: what the other two elements must add up to.
left, right: The two candidates for the pair. Everything between left and right is still possible; everything outside was proven useless for this i.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

arr[left] + arr[right] < need

left++

arr[right] is the largest value left in the range. If even that is not enough for arr[left], no other partner can be. So arr[left] can never be part of the pair.

arr[left] + arr[right] > need

right--

arr[left] is the smallest value left in the range. If even that is too much for arr[right], every other partner is worse. So arr[right] can never be part of the pair.

arr[left] + arr[right] == need

return true

arr[i] + arr[left] + arr[right] == target, and the three positions are different because i < left < right.

left meets right

i++ (try the next fixed element)

Every possible pair for this i has been ruled out.

What does the current window add to the answer?

Each i either finds a pair (and we return true at once) or proves that no triplet has arr[i] as its smallest element. After every i has been tried, every triplet has been covered.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool hasTripletSum(vector<int>& arr, int target) {
        int n = arr.size();
        sort(arr.begin(), arr.end());  // sorting lets us decide which pointer to move

        // Fix the smallest element of the triplet.
        for (int i = 0; i + 2 < n; i++) {
            int need = target - arr[i];
            // Two Sum II on the sorted part to the right of i.
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = arr[left] + arr[right];
                if (sum == need) return true;
                if (sum < need) left++;   // arr[left] is too small even with the largest partner
                else right--;             // arr[right] is too big even with the smallest partner
            }
        }
        return false;
    }
};

import java.util.Arrays;

class Solution {
    public boolean hasTripletSum(int[] arr, int target) {
        int n = arr.length;
        Arrays.sort(arr); // sorting lets us decide which pointer to move

        // Fix the smallest element of the triplet.
        for (int i = 0; i + 2 < n; i++) {
            int need = target - arr[i];
            // Two Sum II on the sorted part to the right of i.
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = arr[left] + arr[right];
                if (sum == need) return true;
                if (sum < need) {
                    left++; // arr[left] is too small even with the largest partner
                } else {
                    right--; // arr[right] is too big even with the smallest partner
                }
            }
        }
        return false;
    }
}

class Solution:
    def hasTripletSum(self, arr: list[int], target: int) -> bool:
        n = len(arr)
        arr.sort()  # sorting lets us decide which pointer to move

        # Fix the smallest element of the triplet.
        for i in range(n - 2):
            need = target - arr[i]
            # Two Sum II on the sorted part to the right of i.
            left, right = i + 1, n - 1
            while left < right:
                s = arr[left] + arr[right]
                if s == need:
                    return True
                if s < need:
                    left += 1  # arr[left] is too small even with the largest partner
                else:
                    right -= 1  # arr[right] is too big even with the smallest partner

        return False

export function hasTripletSum(arr: number[], target: number): boolean {
    const n = arr.length;
    arr.sort((a, b) => a - b); // sorting lets us decide which pointer to move

    // Fix the smallest element of the triplet.
    for (let i = 0; i + 2 < n; i++) {
        const need = target - arr[i];
        // Two Sum II on the sorted part to the right of i.
        let left = i + 1;
        let right = n - 1;
        while (left < right) {
            const sum = arr[left] + arr[right];
            if (sum === need) return true;
            if (sum < need) {
                left++; // arr[left] is too small even with the largest partner
            } else {
                right--; // arr[right] is too big even with the smallest partner
            }
        }
    }
    return false;
}

Complexity

Time O(N²)Space O(1)

Sorting is O(N log N). Then each i runs one two-pointer pass of at most N steps, so O(N²) total. No extra memory apart from the sort.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Three nested loops over i < j < k	O(N³)	O(1)
Better	Fix arr[i]; find a pair summing to target − arr[i] using a set	O(N²)	O(N)
Optimal	Sort; fix arr[i]; move left/right inwards to find the pair	O(N²)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“three elements”Three unknowns → fix one of them in a loop, leaving a pair problem.
“sum equal to target”A pair with a known sum → Two Sum. In a sorted array that is opposite-ends two pointers.
“return true / false”Order and positions don't matter for the answer → we are free to sort.

Pick 3 elements+fixed target sum+order doesn't matter (sorting allowed)→Two Pointers (fix one + opposite ends)

This is the anchor of the k-sum family. The one idea to take away: fix one element, and the rest is Two Sum II on the part to its right. Here we only need yes/no, so there is nothing to deduplicate. The next questions keep this exact loop and add one thing each: collecting every unique triplet (3Sum), tracking the closest sum (3Sum Closest), counting instead of finding (Valid Triangle Number), fixing two elements (4Sum), and counting with repeated values (3Sum With Multiplicity).

Don't make this mistake

Pattern confusion: treating every "pair sum" problem as two pointers

Two pointers works here because we only return true/false, so sorting is harmless. Plain Two Sum (LC 1) asks for the indices of the pair in an unsorted array. Sorting would scramble those indices, so Two Sum is a hash-map problem, not a two-pointer one. Before sorting, always ask: does the answer depend on the original positions?

Using the fixed element twice

✗ int left = 0, right = n - 1;

✓ int left = i + 1, right = n - 1;

If left starts at 0, it can land on i itself, so arr[i] gets counted twice. For arr = [2, 5, 9], target = 9, fixing 2 needs a pair summing to 7, and left = 0 finds 2 + 5 — so it wrongly answers true using the same 2 twice. Searching only to the right of i also avoids checking the same triplet in a different order.

Forgetting to sort

The pointer moves are only safe in a sorted array. Without sorting, sum < need tells you nothing about which element to drop, and the search silently misses triplets.

Allowing left == right

✗ while (left <= right)

✓ while (left < right)

When left == right both pointers sit on one element. Adding it to itself uses one position twice, which the problem does not allow.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

3Sum