The Two Sum problem in Java

Source: Dev.to

Two‑Sum Problem – Different Approaches in Java

The Two‑Sum problem is one of the most common interview questions for developer roles.
Given an array of integers and a target sum, you need to find two numbers in the array whose sum equals the target.

Below are four classic solutions in Java, ordered from the simplest (but slowest) to the most efficient.

1️⃣ Brute‑Force (O(n²) time, O(1) space)

Iterate over each element x and, for every x, scan the rest of the array for a complement y such that x + y == target.

public static int[] getTargetSumIndices(int[] arr, int target) {
    for (int i = 0; i  num) {
            high = mid - 1;
        } else if (arr[mid]  seen = new HashSet<>();

    for (int x : arr) {
        int complement = target - x;
        if (seen.contains(complement)) {
            return new int[]{complement, x}; // found the pair
        }
        seen.add(x);
    }
    return new int[]{-1, -1}; // not found
}

Complexity:

• Time – O(n) (single pass, constant‑time look‑ups).
• Space – O(n) for the hash set.

Summary Table

Choose the implementation that best fits your constraints:

• If you can afford extra space and need the fastest runtime → use the hash‑set method.
• If you must keep space O(1) and the array can be reordered → the two‑pointer technique is ideal.
• For educational purposes or tiny inputs, the brute‑force solution works fine.

Constant‑Time Operations ( O(1) ) for Insertion and Lookup

The code for this approach is as follows:

public static int[] getTargetSumPair(int[] arr, int target) {
    HashSet seen = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        int complement = target - arr[i];
        if (!seen.contains(complement)) {
            seen.add(arr[i]);
        } else {
            return new int[] { arr[i], complement };
        }
    }
    return new int[] { -1, -1 };
}

Complexity Analysis

• Time complexity: O(n) – we iterate through the array once.
  Lookup and insertion operations on a HashSet are O(1) on average.

• Space complexity: O(n) – we store each visited element in the hash set.

Hope you liked reading this blog about the Two Sum problem and the various approaches you can follow to achieve the right result. This is my first algorithm‑related blog on dev.to. Writing blogs has been a really engaging way of learning for me, clarifying my doubts, and sharing my understandings with the community. I aim to clear concepts in a fun way using visual tools like GIFs.

Following this post, I’ll be bringing more such content for the developer community to read and flourish!