Last quarter the same checkout service needed two unpaid invoices that summed to a credit memo. The list was unordered, accounting needed the indexes, and a HashMap of complements was the right bill — that is Two Sum. This quarter the ledger already exports amounts in sorted order, with 1-based row numbers from the CSV. The intern copied the map. Eighty thousand rows still returned. They also allocated eighty thousand extra slots for a question two indexes already answer.

Two Sum II wants two 1-based indexes on already sorted data. An array already gives a[i] for free. Nested search uses that and still pays O(n²).

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here we only care about why the map from unordered Two Sum is the wrong bill once the input is ordered, and why the returned pair is lo + 1, hi + 1.

The problem

Given an int[] numbers already sorted non-decreasing, and an int target, return the two distinct positions of values that add to target. Positions are 1-based: the first slot is 1, not 0. Exactly one solution exists. You may not use the same index twice. Extra space besides the returned pair should stay constant.

numbers = [2, 7, 11, 15], target = 9   →  [1, 2]   because 2 + 7 = 9
numbers = [2, 3, 4],      target = 6   →  [1, 3]   because 2 + 4 = 6
numbers = [-1, 0],        target = -1  →  [1, 2]

Note: Two Sum kept the array unordered so a map could return 0-based indices without permuting them. This prompt already sorted the values. A HashMap still finds the pair; it just spends O(n) extra on a fact two pointers use for free. The + 1 on the way out is the 1-based contract, not a different algorithm.

Nested search is the honest brute force

Every unordered pair is visited once. Correct. Quadratic. You can also, for each i, binary-search target - numbers[i] in the suffix to the right of i. That is O(n log n) — honest, still not the linear walk the sort already paid for.

int[] twoSumNested(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] == target) {
                return new int[] { i + 1, j + 1 };
            }
        }
    }
    throw new IllegalArgumentException("no pair");
}

At n = 20 this is a rounding error. At production size you paid a nested scan (or n binary searches) for a question opposite ends answer in one pass: sum too small, lo++; too large, hi—.

Opposite ends: lo and hi

lo starts at 0, hi at n - 1. Let sum = numbers[lo] + numbers[hi]. Because the array is sorted, that sum tells you which end is wrong. You never restart from index 0. You never allocate a map. Same index cannot pair with itself because the loop is lo < hi.

  • If sum == target, return { lo + 1, hi + 1 }.
  • If sum < target, the left value is too small: lo++.
  • If sum > target, the right value is too large: hi--.
numbers = [2, 7, 11, 15]   target = 9

lo=0 (2),  hi=3 (15)   sum=17  > 9   hi--
lo=0 (2),  hi=2 (11)   sum=13  > 9   hi--
lo=0 (2),  hi=1 (7)    sum=9   == 9  return [1, 2]

The Java is that walk. Add one when you return so the caller gets 1-based indexes:

int[] twoSum(int[] numbers, int target) {
    int lo = 0;
    int hi = numbers.length - 1;
    while (lo < hi) {
        int sum = numbers[lo] + numbers[hi];
        if (sum == target) {
            return new int[] { lo + 1, hi + 1 };
        }
        if (sum < target) {
            lo++;
        } else {
            hi--;
        }
    }
    throw new IllegalArgumentException("no pair");
}

Time is O(n) — each index moves at most once. Space is O(1) extra besides the two-slot result. The HashMap from Two Sum is still correct and the wrong bill: you already have order, so you do not need O(n) memory to remember where a complement sat.

Note: Return lo + 1 and hi + 1. A 0-based pair is a wrong answer on this prompt even when the values are right. Cast the sum to long if they widen the addends; two ints near Integer.MAX_VALUE wrap and a wrapped sum can look “too small.”

What interviewers usually poke next

  • Unsorted input. That is Two Sum. Opposite-end lo++ / hi-- is then a lie; keep the map.
  • 3Sum. Fix i, two-pointer the tail. Values, not indexes. That writeup is 3Sum.
  • Cannot use the same index. lo < hi already refuses it. A lone [4] with target 8 has no pair; two 4s at distinct slots still work.
  • Space strictly O(1). Say why the map is extra you were told not to spend. Binary search per index is the O(n log n) consolation if they forbid both a map and mutating pointers — still slower than opposite ends.

You are done with this problem when you can say, out loud, why unordered Two Sum hashed the complement, why this prompt walks from the ends, and why the returned indexes are one larger than the Java slots.