Two Sum II — Input Array Is Sorted

1. Problem & Core Objective

The problem

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers that add up to a specific target.

Return their indices as [index1, index2] where 1 <= index1 < index2 <= numbers.length.

There is exactly one solution, and you may not use the same element twice.

You must use only constant extra space.

Input:  numbers = [2,7,11,15], target = 9      Output: [1, 2]     (2 + 7 = 9)
Input:  numbers = [2,3,4],     target = 6      Output: [1, 3]     (2 + 4 = 6)
Input:  numbers = [-1,0],      target = -1     Output: [1, 2]

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order
• -1000 <= target <= 1000
• Exactly one solution exists

What the interviewer is actually testing

This is Two Sum with one word changed — "sorted" — and a space constraint added. Both changes are deliberate.

1. Do you notice that the hash map solution is now suboptimal? It still works and is still O(n) — but it uses O(n) space, which the problem explicitly forbids.
2. Can you state the elimination argument? "If the sum is too small, this left element can't pair with anything still in range." That proof is the question.
3. Do you handle the 1-indexed return? A gratuitous detail that catches people who pattern-match from Two Sum.

The lesson of this question is comparative: the same problem has different optimal solutions depending on what structure the input has. Hashing buys you O(n) on unsorted data at the cost of memory; sortedness buys you the same time for free.

2. First-Principles Thought Process

Step 1 — Read the constraints, and notice what changed

n up to 3 × 10^4 — so O(n²) (9 × 10^8) is too slow, and O(n log n) or O(n) is expected.

But two constraints are doing real work:

• "sorted in non-decreasing order" — structure you can exploit.
• "constant extra space" — a hash map is now disallowed, not merely inelegant.

Together these are an instruction: find the solution that uses the ordering instead of memory.

Step 2 — Why the hash map is no longer the answer

The Two Sum approach still works: walk the array, look up target - x in a map. O(n) time. But it costs O(n) space, and the problem forbids it.

More importantly — it ignores the sortedness entirely. Whenever you're handed a structural guarantee and your solution doesn't use it, there's almost always a better one.

Step 3 — What does sortedness actually give you?

In a sorted array, moving right gives you larger values and moving left gives you smaller ones. That means you can steer:

If a sum is too small, you know exactly which direction to go to make it bigger.

That's not available in an unsorted array, where the next element could be anything.

Step 4 — Set up the pointers

Put one pointer at each end:

• lo = 0 — pointing at the smallest value.
• hi = n - 1 — pointing at the largest value.

Their sum starts as the largest-possible-plus-smallest-possible combination. Now compare with the target:

Step 5 — The correctness argument

This is the part worth rehearsing, because it's what gets marked:

"Suppose numbers[lo] + numbers[hi] < target. Since the array is sorted, numbers[hi] is the largest value still in range. So numbers[lo] paired with anything between lo and hi gives a sum that is at most numbers[lo] + numbers[hi] — which is already too small.

Therefore numbers[lo] cannot be part of the answer at all, and I can discard it permanently by moving lo right.

Symmetrically, if the sum is too large, numbers[hi] can't pair with anything remaining, so I discard it."

Picture it as a grid. Imagine the n × n table of all pairs. The brute force checks every cell. Two pointers walk a single path from one corner, and each step deletes an entire row or column. That's how n² candidates collapse to n steps.

Step 6 — Why the loop is lo < hi, not lo <= hi

The two pointers must select distinct elements. If they met (lo == hi), you'd be pairing an element with itself, which the problem forbids.

3. Solution Paths

Approach 1 — Brute force

public int[] twoSum(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};
        }
    }
    return new int[]{};
}

• Time: O(n²).
• Space: O(1).

Ignores the sortedness completely. Name it and move on.

Counter-questions on this approach

⭐ "The array is sorted, and your solution never uses that. What are you leaving on the table?"

Sortedness means one comparison can rule out an entire range of candidates, not just one pair. Whenever I'm handed a structural guarantee and my solution doesn't exploit it, that's almost always a sign a better solution exists — here it's the difference between O(n²) and O(n).

Approach 2 — Hash map (the Two Sum solution)

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        int need = target - numbers[i];
        if (seen.containsKey(need)) return new int[]{seen.get(need) + 1, i + 1};
        seen.put(numbers[i], i);
    }
    return new int[]{};
}

• Time: O(n).
• Space: O(n) — which the problem forbids.

Worth mentioning explicitly, because it demonstrates you know the unsorted version and can see why this one is different: "This is what I'd do if the array weren't sorted, but it uses O(n) space and the problem requires constant."

Counter-questions on this approach

⭐ "That's already O(n) time. Why isn't it the answer?"

Because it's O(n) space, and the problem requires constant. More fundamentally it spends memory to rebuild an ability — finding a value quickly — that the sorted order already provides for free. When the input is sorted, paying for a hash map is paying twice.

"Does this solution use the sortedness anywhere?"

No — and that's the tell. The identical code works on unsorted input. A solution that would be unchanged if a constraint were removed usually isn't the intended one.

Approach 3 — Binary search for each complement

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int need = target - numbers[i];
        int lo = i + 1, hi = numbers.length - 1;       // search only to the RIGHT of i
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (numbers[mid] == need) return new int[]{i + 1, mid + 1};
            if (numbers[mid] < need) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return new int[]{};
}

How it works. For each element, binary search the remaining suffix for its complement. Searching only from i + 1 avoids pairing an element with itself and prevents duplicate answers.

• Time: O(n log n).
• Space: O(1).

A genuine middle ground — it satisfies the space constraint and does use the sortedness. But it uses it only locally (to search), not globally (to eliminate). Two pointers is strictly better.

Worth presenting because it shows you can exploit sortedness in more than one way.

Counter-questions on this approach

⭐ "This is O(1) space and it uses the sortedness. Why isn't it optimal?"

It uses the ordering only locally — to search — and re-searches the remaining suffix from scratch for every element, never remembering what a previous search ruled out. Two pointers is cumulative: every step permanently narrows the range and nothing is ever re-examined. That's the difference between O(n log n) and O(n).

"Why do you search from i + 1 rather than from 0?"

Two reasons: it prevents an element from matching itself, and it stops each pair being discovered twice — once from each end.

Approach 4 — Two pointers (optimal)

public int[] twoSum(int[] numbers, int target) {
    int lo = 0, hi = numbers.length - 1;

    while (lo < hi) {
        int sum = numbers[lo] + numbers[hi];

        if (sum == target) return new int[]{lo + 1, hi + 1};   // 1-INDEXED
        if (sum < target)  lo++;      // need a bigger sum
        else               hi--;      // need a smaller sum
    }
    return new int[]{};               // unreachable — a solution is guaranteed
}

Trace on numbers = [2, 7, 11, 15], target = 9:

Trace on numbers = [2, 3, 4], target = 6:

Trace on numbers = [-1, 0], target = -1:

• Time: O(n) — each iteration moves exactly one pointer, and together they cover at most n positions.
• Space: O(1) — two integers.

Counter-questions on this approach

⭐ "Prove that moving a pointer doesn't skip the answer."

Suppose the sum is too small. The right pointer sits on the largest value still in range, so the left element paired with anything between the pointers gives a sum at most as large — already too small. Therefore the left element cannot participate in any solution and discarding it is safe. The mirror argument applies when the sum is too large.

⭐ "Why lo < hi and not lo <= hi?"

The two pointers must select distinct elements. If they met at lo == hi you'd be pairing an element with itself, which the problem forbids. Binary search uses <= because a single element is a valid answer there; pair-finding uses <.

"Could numbers[lo] + numbers[hi] overflow?"

Not with these constraints — values are bounded by ±1000. If they were near Integer.MAX_VALUE the addition would wrap negative and steer the pointer the wrong way. The fix is to compare numbers[lo] against target - numbers[hi], or widen to long.

"The array is 'non-decreasing' — what if it contains duplicates?"

No special handling needed. Equal values sum identically, and since exactly one solution is guaranteed there's no deduplication requirement.

Comparison

4. Why the Optimal Wins

Against the hash map. Both are O(n) time, so this is entirely about space — and about using what you were given. The hash map spends O(n) memory to reconstruct an ability (finding a value fast) that the sorted order already provides for free. When the input is sorted, paying for a hash map is paying twice.

Against binary search. O(n) beats O(n log n), and the reason is instructive. Binary search re-searches the array from scratch for each element — it never remembers what the previous search ruled out. Two pointers is cumulative: every step permanently narrows the range, and nothing is ever re-examined.

Against brute force. Each two-pointer step eliminates an entire row or column of the pair matrix in a single comparison. That's the whole n² → n collapse.

The comparison to state out loud — this is the real content of the question:

"Two Sum and Two Sum II are the same problem with one difference. On unsorted input you have no structure to exploit, so you buy it with memory — a hash map, O(n) time and O(n) space. On sorted input the structure is already there, so two pointers gets the same O(n) time at O(1) space.

And notably, you can't just sort the unsorted version to get here — sorting destroys the original indices, which is exactly what that problem asks you to return."

Why O(n) is the floor. Every element may need examining; an adversary places the pair wherever you stop looking. So O(n) is optimal, and O(1) space is optimal since two indices suffice.

5. Java Prerequisites

1-indexed return

return new int[]{lo + 1, hi + 1};

The problem uses 1-based indices; Java arrays are 0-based. Forgetting the + 1 is the single most common submission failure on this problem, precisely because everyone arrives from Two Sum where indices are 0-based.

Write the + 1 at the moment you write the return, not as an afterthought.

Overflow safety

int sum = numbers[lo] + numbers[hi];

Here values are bounded by ±1000, so the sum fits easily in an int. If they were near Integer.MAX_VALUE, this addition would overflow and wrap negative, sending the pointer the wrong way.

The overflow-safe alternative avoids adding at all:

if (numbers[lo] == target - numbers[hi]) { ... }        // subtraction instead
// or widen:
long sum = (long) numbers[lo] + numbers[hi];

Mention that you checked the bounds rather than silently relying on them. See 03.

lo < hi vs lo <= hi

while (lo < hi)      // two DISTINCT elements — correct here
while (lo <= hi)     // allows lo == hi, pairing an element with itself

Binary search uses lo <= hi because a single element is a valid answer there. Pair-finding uses lo < hi. Knowing which convention belongs where prevents a whole class of bugs — see 10 — Binary Search.

"Non-decreasing" means duplicates are allowed

[1, 1, 2, 3]      // valid non-decreasing input

The algorithm handles duplicates without any special case: equal values simply sum the same way. Since exactly one solution is guaranteed, there's no dedup requirement either.

6. Interview Communication Guide

Clarifying questions

1. "Is the array sorted ascending, and can it contain duplicates?" — "non-decreasing" means yes to duplicates.
2. "Are the returned indices 0-based or 1-based?" — the problem says 1-based; asking prevents the classic bug.
3. "Is exactly one solution guaranteed?" — yes, which removes the "no answer" branch.
4. "Is there a space constraint?" — the problem says constant; confirming justifies rejecting the hash map out loud.
5. "Can values be negative?" — yes, and the algorithm is unaffected.

The pitch

"This is Two Sum, but the array is sorted and I'm restricted to constant space — so the hash map approach is out, even though it would still be O(n) time.

The sortedness is what I should exploit. I'll put one pointer at each end. If their sum is too small, I move the left pointer right to get a bigger value; if it's too large, I move the right pointer left.

Here's why that's safe: if the sum is too small, the right pointer is already at the largest remaining value — so the left element can't reach the target paired with anything still in range. I can discard it permanently. Same argument mirrored for the other direction.

Each step eliminates a whole row or column of the pair matrix, so O(n²) candidates collapse into O(n) steps. O(n) time, O(1) space.

And the indices are 1-based here, so I'll add one to each on the way out."

Edge cases to raise proactively

The 1-indexing is the detail to state before coding, not after — it's the difference between a correct submission and an off-by-one.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if the array weren't sorted?"

Then I'd use a hash map: one pass, checking for target - x before inserting each element. O(n) time, O(n) space.

And notably I couldn't just sort it first, because sorting destroys the original indices that the unsorted version asks me to return. I'd have to pair each value with its index before sorting, which costs O(n) space anyway — so the hash map is strictly better there.

"What if you needed all pairs summing to the target, not just one?"

Don't return on a match. Record the pair, then move both pointers inward, and skip past duplicates on each side to avoid emitting the same pair twice. That duplicate-skipping is exactly the logic in 3Sum.

"Three Sum on a sorted array?"

Fix the first element with an outer loop, then run this exact two-pointer scan on the remainder. O(n²). That's the next question.

"What if the array is enormous and doesn't fit in memory?"

Two pointers is ideal for this — it reads from both ends and never revisits, so you can stream from the front and back of a file with O(1) memory. The hash map version couldn't do that.

"What if you had to find a pair summing to the target in a BST?"

Same two-pointer idea, but the "ends" are the in-order traversal's start and end. Use two iterators — one going forward (leftmost-first), one backward (rightmost-first) — and compare their sums. O(n) time, O(h) space for the iterator stacks. See 12 — Trees.

"What's the time complexity if you had to sort first?"

O(n log n), dominated by the sort — the two-pointer scan is then free by comparison. That's exactly the accounting in 3Sum, where sorting is O(n log n) but the scan is O(n²), so the sort costs nothing asymptotically.