easyArray ProblemsJava

Find a Pair With a Given Sum in an Array

Determine whether two elements of an array sum to a given target, and report them.

Quick Answer

Scan the array once, keeping a HashSet of values already seen. For each element `v`, check whether `target - v` is in the set; if it is, you have found a pair. Otherwise add `v` and continue. This finds a pair in O(n) time using O(n) extra space.

Problem Statement

Given an integer array and a target sum, determine whether there exist two distinct elements whose values add up to the target, and report one such pair. If no pair exists, report that none was found.

For example, in [2, 7, 11, 15] with target 9, the elements 2 and 7 add up to 9, so that pair is the answer.

Input: An integer array arr of length n and an integer target.

Output: A pair of values summing to target, or a not-found indication.

Examples

Example 1
Input:  arr = [2, 7, 11, 15], target = 9
Output: 2 7

When 7 is reached, its complement 2 is already in the seen set.

Example 2
Input:  arr = [1, 4, 45, 6, 10, 8], target = 16
Output: 6 10

When 10 is reached, its complement 6 has already been seen.

Constraints

  • 2 <= n <= 10^6
  • Values and target fit in a 32-bit int

Think Before You Code

Reveal the questions to ask yourself first
  • For a value v, what other value would complete the pair to reach the target?
  • How can you check in O(1) whether that complement has already appeared?
  • Do you need to look ahead, or only remember what you have already passed?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
For each value `v`, the number you need is `target - v` — its complement.
Hint 2
A HashSet of values seen so far lets you test for the complement in O(1) average time.
Hint 3
Check the set for the complement before adding the current value, so an element is never paired with itself.

Approach

Reveal the step-by-step approach

One pass with a set of seen values.

  1. Create an empty HashSet<Integer>.
  2. For each element v:
    • Compute need = target - v.
    • If need is already in the set, you have found a pair (need, v) — return it.
    • Otherwise add v to the set and continue.
  3. If the loop ends without a match, no pair sums to the target.

Checking the complement before inserting v guarantees the two elements are at different indices.

Dry Run

Walk through the example step by step

Searching arr = [1, 4, 45, 6, 10, 8], target 16:

v  | need = 16 - v | need in set? | set after step
---+---------------+--------------+---------------------
1  | 15            | no           | {1}
4  | 12            | no           | {1,4}
45 | -29           | no           | {1,4,45}
6  | 10            | no           | {1,4,45,6}
10 | 6             | yes -> 6,10  | (return 6 10)

Solution

Reveal the full Java solution
import java.util.HashSet;
import java.util.Set;

public class PairWithGivenSum {
    // Returns a pair {need, v}, or null if none exists.
    public static int[] findPair(int[] arr, int target) {
        Set<Integer> seen = new HashSet<>();
        for (int v : arr) {
            int need = target - v;
            if (seen.contains(need)) {
                return new int[]{need, v};
            }
            seen.add(v);
        }
        return null;
    }

    public static void main(String[] args) {
        int[] p1 = findPair(new int[]{2, 7, 11, 15}, 9);
        System.out.println(p1[0] + " " + p1[1]); // 2 7

        int[] p2 = findPair(new int[]{1, 4, 45, 6, 10, 8}, 16);
        System.out.println(p2[0] + " " + p2[1]); // 6 10
    }
}

Instead of testing every pair in O(n^2), we remember each value we pass and ask a single question at each new element: have I already seen the number that completes this sum? The HashSet answers in O(1) on average, so the whole scan is O(n). Because the complement is looked up before the current value is inserted, no element is ever matched with itself.

Time: O(n)Space: O(n)

Common Mistakes

  • Adding `v` to the set before checking the complement, which can pair an element with itself when target = 2*v.
  • Falling back to a nested-loop O(n^2) scan when the one-pass set approach is available.

Edge Cases to Test

  • No valid pair should return a clear not-found result (here, null).
  • Duplicate values like [3, 3] with target 6 form a valid pair.
  • Negative numbers and negative targets must be handled the same way.

Interview Follow-Ups

  • How would you return the indices of the pair instead of the values?
  • How would you find all distinct pairs that sum to the target?
  • How does a sorted two-pointer approach solve this in O(1) extra space?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us