Two Sum - Find a Pair of Numbers Whose Sum Equals a Target - Java

Category: Medium | Concepts used: HashMap single-pass lookup, two-pointer (sorted variant)

---

Problem Statement

Given an array of integers and a target value, find two numbers that add up to the target. Return their values (or indices, depending on what’s asked).

Input : [2, 7, 11, 15], target = 9      Output: [2, 7]  (2+7=9)

Examples (with edge scenarios)

#	Array	Target	Output	Why
1	[2, 7, 11, 15]	9	[2, 7]	2+7=9
2	[3, 3]	6	[3, 3]	Same value used twice — must be two different elements/indices, not the same one reused
3	[1, 2, 3]	100	No pair found	Target unreachable — must handle gracefully
4	[]	5	No pair found	Empty array — nothing to check
5	[-3, 4, 1, 90]	1	[-3, 4]	Negative numbers work fine too

Common Fresher Mistake

Mistake	What happens	Fix
Using nested loops naively (O(n²)) as the only solution offered	Correct, but not optimal — interviewers usually want to see the O(n) improvement	Know the HashMap-based O(n) solution as your primary answer
Using the SAME element twice (e.g., array has one 3, target is 6, incorrectly returning [3,3] from just one 3)	Logically wrong — needs two distinct positions	Track indices, and ensure you’re not pairing an element with itself unless it genuinely appears twice

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Missing Puzzle Partner

Imagine you are at a party, and each guest has a number card pinned to their chest:

• Solution 1 (Brute Force): You walk around and make every possible pair of guests stand together and add up their cards until you find a pair that equals 9. This takes a long time and is embarrassing.
• Solution 2 (HashMap): You have a clipboard register. You walk from guest to guest:
  • If a guest is holding a 7 and the target is 9, you check if the complement 2 is already written on your clipboard.
  • If it is, you shout: “I’ve found the match!” and point to the guest holding 2 and the current guest.
  • If the complement isn’t on your clipboard, you write down the current guest’s number (7) on your clipboard (seen.put(7, index)) and move to the next person.
• Solution 3 (Two Pointers - Sorted Line): You line up all the guests from shortest card number to tallest card number.
  • You compare the sum of the extreme left (smallest) and extreme right (largest) guests.
  • If their sum is too small, you need a larger number, so you look at the next person on the left.
  • If their sum is too large, you need a smaller number, so you look at the next person on the right.

---

Solution 1 — Brute Force with Nested Loops

Intuition

The simplest way to find a pair summing to the target is to literally try every possible pair — for each element, check it against every element that comes after it, and see if they add up to the target.

public class TwoSumBruteForce {
    public static int[] twoSum(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == target) {
                    return new int[]{arr[i], arr[j]};
                }
            }
        }
        return new int[]{}; // no pair found
    }

public static void main(String[] args) {
        int[] result = twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(java.util.Arrays.toString(result)); // [2, 7]
    }
}

Output:

[2, 7]

Dry Run (arr=[2,7,11,15], target=9)

i=0(2): j=1(7) -> 2+7=9 -> MATCH! return [2,7]  (no need to check further pairs)

Interviewer’s take

Correct, but O(n²) — checking every pair is wasteful. This is a fine opening answer to show you understand the problem, but interviewers will almost always ask for something faster.

Follow-up questions you might get:

• “Can you solve this in a single pass, O(n) time?” → leads to Solution 2.

---

Solution 2 — Using a HashMap (Single Pass, Recommended)

Intuition

For each number, instead of searching the rest of the array for its “partner” (target minus current number), we can remember every number we’ve already seen in a HashMap. Then, before adding the current number to that memory, we just check: “have I already seen the number that would complete the pair (target - current)?” If yes, we’ve found our answer instantly — no nested search needed.

import java.util.HashMap;

public class TwoSumHashMap {
    public static int[] twoSum(int[] arr, int target) {
        HashMap<Integer, Integer> seen = new HashMap<>(); // value -> index

for (int i = 0; i < arr.length; i++) {
            int complement = target - arr[i]; // the value we're looking for

if (seen.containsKey(complement)) {
                return new int[]{complement, arr[i]}; // found the pair!
            }
            seen.put(arr[i], i); // remember this value for future checks
        }
        return new int[]{}; // no pair found
    }

public static void main(String[] args) {
        int[] result = twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(java.util.Arrays.toString(result)); // [2, 7]

int[] result2 = twoSum(new int[]{3, 3}, 6);
        System.out.println(java.util.Arrays.toString(result2)); // [3, 3]
    }
}

Output:

[2, 7]
[3, 3]

Dry Run (arr=[2,7,11,15], target=9)

seen = {}

i=0: arr[0]=2, complement=9-2=7 -> seen.containsKey(7)? no -> seen.put(2,0) -> seen={2:0}
i=1: arr[1]=7, complement=9-7=2 -> seen.containsKey(2)? YES! -> return [2, 7]

Dry Run (arr=[3,3], target=6) — testing the “same value twice” edge case

seen = {}

i=0: arr[0]=3, complement=6-3=3 -> seen.containsKey(3)? no (nothing added yet) -> seen.put(3,0) -> seen={3:0}
i=1: arr[1]=3, complement=6-3=3 -> seen.containsKey(3)? YES (from index 0) -> return [3, 3]

Interviewer’s take

This is the preferred final answer — O(n) time, O(n) space, single pass. The key subtlety interviewers watch for: checking seen.containsKey(complement) before adding the current number to seen — this naturally prevents pairing an element with itself unless a genuine duplicate exists earlier in the array (as demonstrated in the [3,3] dry run above).

Follow-up questions you might get:

• “Why check containsKey before adding the current number, not after?” → If we added first, a single 3 with target 6 could incorrectly “find itself” as its own complement — checking first ensures we only match against numbers seen before the current one.
• “What if the array is already sorted? Is there a way to avoid extra space?” → Yes — leads to Solution 3.

---

Solution 3 — Two Pointers (Only if the Array is Already Sorted)

Intuition

If the array is sorted, place one pointer at the start (smallest value) and one at the end (largest value). If their sum is too small, the only way to increase it is to move the left pointer right (toward bigger values). If the sum is too big, move the right pointer left (toward smaller values). This converges on the answer without needing any extra memory.

import java.util.Arrays;

public class TwoSumTwoPointer {
    public static int[] twoSum(int[] sortedArr, int target) {
        int left = 0, right = sortedArr.length - 1;

while (left < right) {
            int sum = sortedArr[left] + sortedArr[right];
            if (sum == target) {
                return new int[]{sortedArr[left], sortedArr[right]};
            } else if (sum < target) {
                left++;  // need a bigger sum, move left pointer up
            } else {
                right--; // need a smaller sum, move right pointer down
            }
        }
        return new int[]{};
    }

public static void main(String[] args) {
        int[] sorted = {2, 7, 11, 15}; // already sorted
        System.out.println(Arrays.toString(twoSum(sorted, 9))); // [2, 7]
    }
}

Output:

[2, 7]

Interviewer’s take

This is a great bonus if the input is guaranteed sorted (or if the interviewer allows sorting first) — O(1) extra space compared to the HashMap’s O(n). Only applicable when order is known/sortable; if the original indices need preserving, sorting would lose that unless you track them separately.

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr, target T"] --> Method{"Method Selection"}
    Method -->|Unsorted: HashMap| MapApproach["Initialize seen Map<br>i = 0"]
    MapApproach --> LoopMap{"i < arr.length?"}
    LoopMap -->|Yes| Comp["complement = T - arr[i]"]
    Comp --> CheckMap{"seen.containsKey(complement)?"}
    CheckMap -->|Yes| RetMap["Return [complement, arr[i]]"]
    CheckMap -->|No| StoreMap["seen.put(arr[i], i)<br>i++"]
    StoreMap --> LoopMap
    LoopMap -->|No| RetEmpty["Return empty array"]
    Method -->|Sorted: Two Pointer| SortApproach["left = 0, right = arr.length - 1"]
    SortApproach --> LoopPtr{"left < right?"}
    LoopPtr -->|Yes| SumCheck["sum = arr[left] + arr[right]"]
    SumCheck --> Match{"sum == T?"}
    Match -->|Yes| RetPtr["Return [arr[left], arr[right]]"]
    Match -->|No| SizeCheck{"sum < T?"}
    SizeCheck -->|Yes| MoveLeft["left++"]
    SizeCheck -->|No| MoveRight["right--"]
    MoveLeft --> LoopPtr
    MoveRight --> LoopPtr
    LoopPtr -->|No| RetEmpty

---

Final Verdict — Which Solution Should You Give?

• Solution 2 (HashMap) is the expected final answer for the general (unsorted) case — this is one of the most famous interview questions, and the HashMap approach is considered the standard solution.

---

Quick Recap

Approach	Time	Space	Requires sorted input?
Nested loops	O(n²)	O(1)	No
HashMap	O(n)	O(n)	No
Two-pointer	O(n)	O(1)	Yes