Difficulty: MediumTwo Pointers

Two Sum II (Sorted Array)

Problem in Plain English

Given a 1-indexed array numbers sorted in non-decreasing order and an integer target, find the two positions whose values add up to target and return them as [index1, index2]. Exactly one solution exists, no element may be used twice, and only constant extra space may be used.

Problem Statement

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 integer target.

Return the two indices, each increased by one, as [index1, index2] with index1 < index2. Exactly one solution exists, the same element may not be used twice, and the solution must use only constant extra space.

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, and the same element may not be used twice.

Examples

Example 1

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Values 2 and 7 at 1-based positions 1 and 2 sum to 9, the only valid pair.

Example 2

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Values 2 and 4 at 1-based positions 1 and 3 sum to 6.

Example 3

Input: numbers = [-1,0], target = -1
Output: [1,2]

Values -1 and 0 at 1-based positions 1 and 2 sum to -1.

Example 4

Input: numbers = [2, 2, 3], target = 4
Output: [1, 2]

The two equal values occupy distinct positions and form the unique valid pair. Using one occurrence twice would be invalid.

Example 5

Input: numbers = [1, 2, 4, 6], target = 8
Output: [2, 4]

The endpoint sum 1 + 6 is too small, so discard 1. Then 2 + 6 = 8 gives one-based indices 2 and 4.

Intuition

Sorted order makes each sum comparison a safe elimination. In [2, 7, 11, 15] with target 9, the smallest plus largest is 17. Even the smallest value is too large to pair with 15, so 15 cannot participate; remove that endpoint. Repeating this leaves 2 and 7. Return their positions as 1 and 2 because the answer uses one-based indexing. Equal values may form the pair if they occupy different positions.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Trying every pair of positions and testing its sum is guaranteed to stumble on the single valid pair. Sorted order is simply ignored here, which is why the same scan works on any array.

Step-by-Step Logic

For each index i, try every later index j starting at i + 1. This checks two distinct positions without modifying the sorted input.
Compute numbers[i] + numbers[j]. When it equals target, return [i + 1, j + 1]. Example 1 first tries i = 0 and j = 1, so 2 + 7 = 9 immediately matches.
If a pair misses, continue through later j values, then advance i. The unique-solution guarantee ensures some tested pair returns; the final empty-list return is only a defensive fallback outside that guarantee.

Why It Works

Every possible pair of different indices has exactly one ordering i < j. The loops inspect those pairs until the guaranteed matching pair is found. Equality verifies the target sum, and adding one converts both positions to the required one-based indices while preserving their increasing order.

Dry Run

Brute Force: variable states at each step
i	j	numbers[i] + numbers[j]	Target 9	Result
0	1	2 + 7 = 9	Match	Return [1, 2]
-	-	Search stops	-	[1, 2] confirmed

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

There are at most n(n - 1)/2 index pairs, giving O(n^2) worst-case time when the match is late. Example 1 returns after one comparison, but that does not determine the worst-case bound. Only two indices and a fixed-size two-element return array are stored, so extra space is O(1).

Code

Solution.java

1class Solution {2    public int[] twoSum(int[] numbers, int target) {3        for (int i = 0; i < numbers.length; i++) {4            for (int j = i + 1; j < numbers.length; j++) {5                if (numbers[i] + numbers[j] == target) {6                    return new int[] { i + 1, j + 1 };7                }8            }9        }10        return new int[0];11    }12}

Hints

Hint 1

Sorted order tells you how a sum changes when either end moves, so what does a too-small sum say about the left value?

Hint 2

Pin the smallest and largest remaining values; one of them can always be ruled out from the current sum.

Hint 3

Remember the required answer uses 1-based positions, so each pointer needs + 1 on the way out.

Edge Cases

Two elements, such as [-1, 0] with target -1, are already the answer at initialization.
Equal values at separate positions are allowed: [2, 2, 3] with target 4 returns [1, 2].
Negative values do not change elimination rules because those rules rely on order, not positivity.
An answer at the far ends may return immediately; a pair near one end can require a full linear scan.
Exactly one valid index pair is guaranteed. An unsorted array or no-solution input violates the contract; the defensive empty return is not an expected problem output.
Pair sums lie in [-2000, 2000] under the constraints, safely represented by Java int and JavaScript Number.

Common Mistakes and Interview Tips

Returning zero-based pointers instead of adding one to each required index.
Using left <= right can reuse the same element. Require left < right, even when target is twice one value.
Moving both pointers after a mismatch can skip the solution. Move only the endpoint proved impossible by sorted order.
Sorting again is unnecessary and can disrupt original positions. A hash map also breaks the explicit constant-extra-space requirement.
Interview tip: demonstrate both too-large and too-small cases, justify why all pairs involving the discarded endpoint fail, and contrast linear elimination with binary search per element or quadratic pair enumeration.

Key Takeaway

On sorted input, opposite endpoints bound all remaining pair sums. Each comparison safely removes one impossible endpoint, yielding a linear scan with constant storage; this is elimination by order, not binary search.