Solution: Brute Force

We take each element in the array and check whether there is another element that adds up to the target with it. That means checking every possible pair, which is two nested loops. The outer loop picks the first element of the pair and the inner loop picks the second. Here is how it looks in code:

public static int[] twoSum(int[] numbers, int target) {
  for (int i = 0; i < numbers.length - 1; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] == target) {
        return new int[]{i, j};  // Found it!
      }
    }
  }
  return new int[0];  // We never reach here because the problem guarantees a solution exists
}

Returning an empty array

The return new int[0]; line is never reached because the problem guarantees that a solution exists. We include it to satisfy the compiler, which requires that all code paths return a value.

We could also return null; or throw an exception. Returning an empty array is considered best practice. It conforms to standard programming idioms designed to prevent runtime crashes and streamline code readability.

Before we work out the Big-Oh, let’s trace it, because the trace shows how many comparisons the loops do. Take numbers = [2, 7, 11, 15] with target = 26. The answer is the pair at i = 2, j = 3, since 11 + 15 = 26, and that pair is at the very end of the array. That is the worst place for it to be, so this trace is the worst case. The outer loop fixes i, and the inner loop moves j across every element to the right of i.

We start with i at index 0. The inner loop pairs numbers[0] with each later element:

┌────┬────┬────┬────┐
│  2 │  7 │ 11 │ 15 │
└────┴────┴────┴────┘
   ↑    ↑
   i    j

2 + 7 = 9, too small, so j keeps advancing until the inner loop finishes:

┌────┬────┬────┬────┐
│  2 │  7 │ 11 │ 15 │
└────┴────┴────┴────┘
   ↑              ↑
   i              j

None of those pairs add up to 26, so the outer loop advances to i = 1 and j restarts just past i:

┌────┬────┬────┬────┐
│░ 2░│  7 │ 11 │ 15 │
└────┴────┴────┴────┘
        ↑    ↑
        i    j

The shaded elements to the left of i have already been used as the first element of a pair.

Again j moves to the end without a match (7 + 15 = 22, still too small):

┌────┬────┬────┬────┐
│░ 2░│  7 │ 11 │ 15 │
└────┴────┴────┴────┘
        ↑         ↑
        i         j

The inner loop finds the answer when i reaches index 2: 11 + 15 = 26.

┌────┬────┬────┬────┐
│░ 2░│░ 7░│ 11 │ 15 │
└────┴────┴────┴────┘
             ↑    ↑
             i    j

Because the match was at the far end, we checked every pair the two loops can form before we found it.

The loops are nested, so their work multiplies. The outer loop runs about $n$ times and the inner loop runs up to $n$ times for each of those, so the comparison inside runs up to $n \times n = n^{2}$ times, with constant work each. That is $O (n^{2})$ .

The inner loop starts at i + 1 rather than at 0, so we are really checking each pair once instead of twice, and the count is the triangular number $\frac{n ( n - 1 )}{2}$ rather than $n^{2}$ . That is the same count we saw in hasDuplicates. Drop the constant factor $\frac{1}{2}$ , drop the lower-order term, and it is $O (n^{2})$ either way.