Find Three Elements that Sum to a Target

Title: Find Three Elements that Sum to a Target

In this guide, you’ll learn how to find three elements in an array that add up to a given target sum, a classic interview problem usually called 3Sum. We’ll build a sort-and-two-pointer solution, trace it step by step on a concrete input, and cover the common mistakes, edge cases, and follow-up questions that come up when solving it under interview conditions.

Understanding the Problem

Given an array of integers called numbers and an integer called target, the goal is to find three elements at three distinct indices whose sum equals target. If such a triplet exists, return it. Otherwise, report that no triplet was found.

The naive approach checks every combination of three elements with three nested loops, which costs O(n^3) time. Sorting the array first lets you fix one element and scan the rest with two pointers in O(n) time, bringing the total cost down to O(n^2).

Approach

The sort-and-two-pointer approach follows these steps.

1. Clone the input array and sort it in ascending order so the two-pointer scan can rely on ordering.
2. Loop an index i from 0 up to length - 3, treating numbers[i] as the fixed first element of the triplet.
3. Set left to i + 1 and right to the last index of the array.
4. While left is less than right, compute currentSum as the sum of the elements at i, left, and right.
5. If currentSum equals target, return the triplet immediately.
6. If currentSum is less than target, increment left to increase the sum.
7. If currentSum is greater than target, decrement right to decrease the sum.
8. If the outer loop finishes without a match, return null to signal that no triplet exists.

Java Program

Here is the complete, compilable program.

import java.util.Arrays;

public class ThreeSumToTarget {

    public static int[] findTripletWithSum(int[] numbers, int target) {
        int[] sorted = numbers.clone();
        Arrays.sort(sorted);

        for (int i = 0; i < sorted.length - 2; i++) {
            int left = i + 1;
            int right = sorted.length - 1;

            while (left < right) {
                int currentSum = sorted[i] + sorted[left] + sorted[right];

                if (currentSum == target) {
                    return new int[] { sorted[i], sorted[left], sorted[right] };
                } else if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] numbers = { 12, 3, 4, 1, 6, 9 };
        int target = 24;

        int[] triplet = findTripletWithSum(numbers, target);

        if (triplet != null) {
            System.out.println("Triplet found: " + Arrays.toString(triplet));
        } else {
            System.out.println("No triplet found with the given target.");
        }
    }
}

Explanation of the Program

• The method findTripletWithSum calls numbers.clone() before sorting, so the caller’s original array is never reordered.
• The outer loop stops at sorted.length - 2 because left and right always need at least two remaining elements after i.
• Inside the while loop, left and right converge toward each other. Every comparison moves exactly one pointer, so the loop never re-checks a pair it has already ruled out.
• As soon as currentSum matches target, the method returns immediately via return new int[] { sorted[i], sorted[left], sorted[right] }. If every i is exhausted with no match, it returns null.

Step-by-Step Trace

Trace findTripletWithSum on numbers = {1, 4, 6, 8, 10, 45} with target = 22. The array is already sorted, and the expected output is the triplet {4, 8, 10}.

At the start of every comparison, the pair that the moving pointer just skipped is guaranteed not to sum to target with the current fixed element, so the search space shrinks by at least one pair on every step until a match is found or left meets right.

Examples

Example 1: Triplet Exists

A straightforward case where a valid triplet is present in the array.

// Input: numbers = {12, 3, 4, 1, 6, 9}, target = 24
int[] result = findTripletWithSum(new int[] { 12, 3, 4, 1, 6, 9 }, 24);
System.out.println(Arrays.toString(result));
// Output: [3, 9, 12]

Example 2: No Triplet Found

When no three elements can reach the target, the method returns null instead of throwing or guessing.

// Input: numbers = {1, 2, 4, 8}, target = 100
int[] result = findTripletWithSum(new int[] { 1, 2, 4, 8 }, 100);
System.out.println(result == null ? "No triplet found" : Arrays.toString(result));
// Output: No triplet found

Example 3: Negative Numbers

The two-pointer logic works unchanged when the array mixes negative and positive values, since it only relies on sorted order, not on sign.

// Input: numbers = {-5, 2, -1, -4, 3, 7}, target = -3
int[] result = findTripletWithSum(new int[] { -5, 2, -1, -4, 3, 7 }, -3);
System.out.println(Arrays.toString(result));
// Output: [-5, -1, 3]

Common Mistakes to Avoid

These are the slip-ups that actually show up when candidates implement this pattern.

• Forgetting to sort first – the two-pointer decision of moving left versus right only makes sense on sorted data. Skipping Arrays.sort(sorted) produces wrong or missing triplets even though the loop logic looks correct. Always sort a clone of the array before scanning.
• Looping i too far – using i < sorted.length instead of i < sorted.length - 2 lets left and right run out of room, throwing ArrayIndexOutOfBoundsException on the last one or two iterations. Stop the outer loop two elements before the end.
• Returning sorted-array values as if they were original indices - once you clone and sort, the positions no longer match the caller's array. If the caller needs original indices, search for each returned value's first occurrence in the unsorted array instead of reusing loop indices.
• Ignoring integer overflow on the sum - adding three values near Integer.MAX_VALUE can silently overflow and flip the sign of currentSum, making the comparison against target wrong without any exception. Use a long for currentSum when the input range is not bounded.

Edge Cases to Test

Walking through these boundary inputs out loud is exactly what interviewers want to see before you start coding.

• Array with fewer than three elements
• No triplet sums to target
• All elements identical
• Duplicate elements forming the triplet (such as three zeros)
• Target achievable only using negative numbers
• Multiple valid triplets exist (only the first one found is returned)
• Integer.MAX_VALUE or Integer.MIN_VALUE present
• Null array reference

Additional Considerations

Sorting the array costs O(n log n) with Arrays.sort, but the double loop that follows costs O(n^2), so the overall time complexity is O(n^2). The space cost is O(n) for the cloned array, plus the small, constant stack and auxiliary space that the dual-pivot quicksort used by Arrays.sort needs for primitive arrays.

This beats the brute-force triple loop at O(n^3), and it avoids the O(n) extra space a hash-set approach would need to track complements. The trade-off is that sorting reorders the data, so this approach is a poor fit when the original index positions of the matching elements must be preserved.

Integer.MIN_VALUE and Integer.MAX_VALUE matter specifically because of the overflow risk discussed above; a triplet containing both can push currentSum past the range of int even though each individual value is valid.

Interview Follow-up Questions

Expect an interviewer to push past the base problem with questions like these.

• What if you need all unique triplets instead of just one? - after finding a match, skip past duplicate values at both left and right before continuing, and skip duplicate values of i as well, so the same triplet is never collected twice.
• What if you need four elements that sum to a target (4Sum)? - fix the first two elements with a nested loop, then run this same two-pointer scan on the remaining range; the complexity rises to O(n^3).
• What if the array is read-only and cannot be sorted in place? - sort an array of indices by their corresponding values instead of sorting the original array, so the original order and the result's original indices are both preserved.
• What if the numbers arrive as a stream of unknown length? - the two-pointer scan needs random access to sorted data, which a stream does not offer; you would need to buffer and sort in batches, or fall back to a hash-based approach with higher memory use.

Conclusion

The sort-and-two-pointer technique turns an O(n^3) brute-force search into an O(n^2) scan, and the same pattern extends directly to 4Sum, closest-sum, and count-of-triplets variants. Once you are comfortable tracing how left and right converge, try adapting the program to return every unique triplet instead of just the first match.

You can learn more about array-based interview problems in the Arrays category on Daily Java Concept.