☕ DSA Java Articles

Topics › Arrays › Medium

Two Sum

Easy TUF ID 37 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums and an integer target. Return the indices i and j (with i < j) of two different elements whose values add up to target. If no such pair exists, return {-1, -1}. Some versions of the problem only ask whether such a pair exists; the same approaches answer that too.

Constraints: 2 ≤ n ≤ 10^5, values and target fit in a 32-bit signed integer. Exactly one valid answer exists in the LeetCode version.

Example 1

nums = [2, 7, 11, 15], target = 9
answer = [0, 1]          // 2 + 7 = 9

Example 2

nums = [3, 3], target = 6
answer = [0, 1]          // the two 3s are different elements, so this is allowed

Example 3

nums = [1, 2, 3], target = 7
answer = [-1, -1]        // no two elements sum to 7

Approach 1: Brute force

Intuition. The definition of the problem is “some pair sums to target”, so the most direct method is to look at every pair. Fix the first element with an outer loop, and scan everything after it with an inner loop. Starting the inner loop at i + 1 guarantees we never pair an element with itself and never check the same pair twice.

Algorithm.

  1. For every index i from 0 to n - 1:
  2. For every index j from i + 1 to n - 1:
  3. If nums[i] + nums[j] == target, return {i, j}.
  4. If the loops finish, return {-1, -1}.
static int[] bruteForce(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((long) nums[i] + nums[j] == target) return new int[]{i, j};
        }
    }
    return new int[]{-1, -1};
}

Complexity. Time O(n^2): there are n(n-1)/2 pairs and each is checked in constant time. Space O(1): only loop counters.

The (long) cast matters. Two values near 2 × 10^9 add up to about 4 × 10^9, which does not fit in an int; the wrapped-around result could accidentally equal the target and report a pair that does not really exist.

For n = 10^5 that is about 5 × 10^9 comparisons, which will not pass in time. We need to avoid checking every pair.

Approach 2: Better, sorting plus two pointers

Intuition. If the array were sorted, we could place one pointer at the smallest value and one at the largest. If their sum is too small, the only way to increase it is to move the left pointer right. If the sum is too big, move the right pointer left. Each step discards one element for good, so we finish in one linear sweep.

The catch is that the question asks for the original indices, and sorting destroys them. So we sort pairs of {value, originalIndex} instead of bare values.

Algorithm.

  1. Build an array of {value, originalIndex} pairs and sort it by value.
  2. Set lo = 0 and hi = n - 1.
  3. While lo < hi: compute sum = value[lo] + value[hi].
    • If sum == target, return the two original indices in increasing order.
    • If sum < target, do lo++. Otherwise do hi--.
  4. Return {-1, -1} if the pointers meet.
static int[] better(int[] nums, int target) {
    int n = nums.length;
    int[][] a = new int[n][2];               // {value, originalIndex}
    for (int i = 0; i < n; i++) a[i] = new int[]{nums[i], i};
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        long sum = (long) a[lo][0] + a[hi][0];
        if (sum == target) {
            int i = Math.min(a[lo][1], a[hi][1]), j = Math.max(a[lo][1], a[hi][1]);
            return new int[]{i, j};
        }
        if (sum < target) lo++; else hi--;
    }
    return new int[]{-1, -1};
}

Complexity. Time O(n log n) for the sort; the two-pointer sweep is O(n). Space O(n) for the array of pairs.

Note the long cast in the sum. Two values near 2 × 10^9 overflow int when added, and an overflowed sum could accidentally equal the target.

This approach is the one to remember when the problem is a yes/no question or when the input is already sorted, because then no index bookkeeping is needed and the extra space disappears.

Approach 3: Optimal, one pass with a hash map

Intuition. While scanning left to right, at position j we want to know: “have I already seen the value target - nums[j], and if so, where?” A hash map from value to index answers that in constant time. Insert each element after checking, so an element can never be paired with itself.

Algorithm.

  1. Create an empty map seen from value to index.
  2. For each index j: let need = target - nums[j].
    • If need is in seen, return {seen.get(need), j}.
    • Otherwise store seen.put(nums[j], j).
  3. Return {-1, -1} if the loop finishes.

One subtlety: target - nums[j] can itself overflow int (for example -294967296 - 2000000000). Computing need as a long and skipping the lookup when it is outside the int range keeps the method exact; any value outside that range cannot be in the array anyway.

static int[] optimal(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int j = 0; j < nums.length; j++) {
        long need = (long) target - nums[j];           // long: target - nums[j] can overflow int
        if (need >= Integer.MIN_VALUE && need <= Integer.MAX_VALUE) {
            Integer i = seen.get((int) need);
            if (i != null) return new int[]{i, j};
        }
        seen.put(nums[j], j);
    }
    return new int[]{-1, -1};
}

Dry run on nums = [2, 7, 11, 15], target = 9:

j nums[j] need need in seen? action
0 2 7 no seen = {2→0}
1 7 2 yes, index 0 return {0, 1}

Complexity. Time O(n): one pass, each map operation is O(1) on average. Space O(n) for the map in the worst case.

Because duplicates are stored with their latest index only after the check, [3, 3] with target 6 correctly returns {0, 1}: at j = 1, need = 3 is already present from j = 0.

Edge cases and pitfalls