Loading…

mediumArraysLC #167Frequently asked

Two Sum II — Input Array Is Sorted

Q: How do you solve Two Sum II — Input Array Is Sorted using the Brute Force — Nested Pair Scan approach?

When to use it: Mention briefly to anchor the progression, then immediately note it ignores the 'sorted' gift and is strictly worse. The mechanical translation of the prompt: fix the first index `i`, sweep every later index `j`, and check whether the two values add to `target`. Return the 1-indexed pair on the first hit. **Why mention it at all.** Even though it's quadratic, stating it shows you derive the optimal from a baseline rather than memorizing. It also lets you contrast: 'this works on *any* array, sorted or not — which is exactly why it's wasteful here.' **Why it throws away the key fact.** The problem went out of its way to tell you the array is **sorted**. Brute force never reads that signal — it would run identically on a shuffled array. Any time the interviewer hands you a precondition and your algorithm ignores it, you're leaving the intended solution on the table. **Why we don't ship it.** With `n` up to `3 × 10⁴`, `n²/2` is ~450 million comparisons — borderline and pointless when the sorted structure gives you a linear sweep for free. State it, name its cost, and pivot to two pointers in the same breath. Time complexity: O(n²). Space complexity: O(1).

LCPractice

Two Pointers · 8 of 30 · 9 min

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

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2, where 1 ≤ index1 < index2 ≤ numbers.length.

The tests are generated such that there is **exactly one solution**. You may not use the same element twice. Your solution must use only constant extra space.

In plain English

It's Two Sum with two twists: the array is already sorted, and the answer must be 1-indexed. The sorted guarantee unlocks an O(1)-space two-pointer sweep, and the constant-space requirement explicitly forbids the hash-map approach you'd use for unsorted Two Sum.

Examples

Example 1

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Note: 2 + 7 = 9. Their 1-indexed positions are 1 and 2.

Example 2

Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]
Note: 2 + 4 = 6. Positions 1 and 3.

Example 3

Input: numbers = [-1, 0], target = -1
Output: [1, 2]
Note: -1 + 0 = -1. Negatives work with no special handling.

Constraints

2 ≤ numbers.length ≤ 3 × 10⁴
-1000 ≤ numbers[i] ≤ 1000
numbers is sorted in non-decreasing order
-1000 ≤ target ≤ 1000
Exactly one valid answer exists
Must use O(1) extra space

Clarifying questions4First question: Is the array guaranteed sorted, and in which order?Explore questions

Q1.Is the array guaranteed sorted, and in which order?
Yes — non-decreasing. That precondition is the entire reason two pointers works; without it you'd be back to a hash map.
Q2.Are the returned indices 0-indexed or 1-indexed?
1-indexed. The prompt says 'added by one'. Returning [lo, hi] instead of [lo + 1, hi + 1] is the most common silent failure.
Q3.Is there always exactly one solution?
Yes. So I can return immediately on the first matching pair without worrying about ties.
Q4.Can the values be negative or duplicated?
Both. Negatives are fine — the comparison logic doesn't assume positivity. Duplicates are fine too because lo < hi guarantees two distinct positions.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The array is sorted — that single fact kills the hash map. Put one pointer at each end and look at the sum: if it's too big, move the right pointer left; if it's too small, move the left pointer right. O(n) time, O(1) space. Return 1-indexed positions, not 0-indexed.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit the 'sorted' precondition instead of blindly reusing the Two Sum hash map. The whole problem is a one-word change ('sorted') that should change your entire approach.

Where candidates slip

Returning 0-indexed answers (the prompt demands 1-indexed), or reaching for a hash map and throwing away the O(1)-space win the sorted input hands you for free.

How to stand out

Say out loud: 'Because it's sorted, I can converge two pointers from the ends in O(1) space — strictly better than the hash map I'd use for unsorted Two Sum.' Then justify *why* moving each pointer is correct.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Nested Pair Scan	`O(n²)`	`O(1)`	Mention briefly to anchor the progression, then immediately note it ignores the 'sorted' gift and is strictly worse.	Read
2	Opposite-End Two Pointers (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Lead with 'because it's sorted' — that justification is the whole point of the medium rating.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind a pair summing to targetIs the array sorted?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Nested Pair Scan

TimeO(n²)SpaceO(1)

Mention briefly to anchor the progression, then immediately note it ignores the 'sorted' gift and is strictly worse.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the sorted property for a moment. What's the most literal way to find a pair that sums to target?

2Hint 2Explore hint

Try every pair (i, j) with j > i and test numbers[i] + numbers[j] == target.

3Hint 3Explore hint

Two nested loops; return [i + 1, j + 1] on the first match. Note: this wastes the sorted order entirely.

A · Core idea

The mechanical translation of the prompt: fix the first index i, sweep every later index j, and check whether the two values add to target. Return the 1-indexed pair on the first hit.

Why mention it at all. Even though it's quadratic, stating it shows you derive the optimal from a baseline rather than memorizing. It also lets you contrast: 'this works on any array, sorted or not — which is exactly why it's wasteful here.'

Why it throws away the key fact. The problem went out of its way to tell you the array is sorted. Brute force never reads that signal — it would run identically on a shuffled array. Any time the interviewer hands you a precondition and your algorithm ignores it, you're leaving the intended solution on the table.

Why we don't ship it. With n up to 3 × 10⁴, n²/2 is ~450 million comparisons — borderline and pointless when the sorted structure gives you a linear sweep for free. State it, name its cost, and pivot to two pointers in the same breath.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numbers = [2, 7, 11, 15], target = 9

i=0, j=1

2 + 7 = 9

Statematch → return [1, 2]

Final result[1, 2]

C · Code with teaching comments

Reference implementation previewpublic 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};Explore the full code

solution.javaJava

Brute Force — Nested Pair Scan — reference

2 teaching notes

1
public int[] twoSum(int[] numbers, int target) {
2
    for (int i = 0; i < numbers.length; i++) {
3
        // j starts at i+1 to avoid self-pairing and rechecking reversed pairs.
4
        for (int j = i + 1; j < numbers.length; j++) {
5
            if (numbers[i] + numbers[j] == target) {
6
                // 1-indexed output — add one to each position.
7
                return new int[]{i + 1, j + 1};
8
            }
9
        }
10
    }
11
    return new int[]{-1, -1};
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force is precondition-blind: it would behave the same on an unsorted array. The moment you notice your candidate solution doesn't use a stated property ('sorted'), that's your cue a better algorithm exists.

ComplexityO(n²) time, O(1) space — n(n−1)/2 ≈ n²/2 comparisons in the worst case; no extra data structures, so O(1) space.

E · Edge cases and pitfalls3Returning [i, j] instead of [i + 1, j + 1] — this problem is 1-indexed.Explore edge cases

Pitfalls

Returning [i, j] instead of [i + 1, j + 1] — this problem is 1-indexed.
Ignoring the 'sorted' precondition entirely — the signal that a better answer exists.
Starting j at 0 — reuses an element with itself.

03.2

Approach 2 of 2 · Optimal

Opposite-End Two Pointers (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Lead with 'because it's sorted' — that justification is the whole point of the medium rating.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array is sorted. If you stand one pointer at the smallest value and one at the largest, what does their sum tell you about which value to swap out?

2Hint 2Explore hint

If the sum is too big, the only way to shrink it without losing reachable pairs is to move the right pointer left. If it's too small, move the left pointer right.

3Hint 3Explore hint

Loop while lo < hi. On equality return [lo + 1, hi + 1]. Each step discards exactly one element that can't be part of any answer — that's why it's O(n).

A · Core idea

Place lo at index 0 (smallest value) and hi at index n − 1 (largest value). Compute sum = numbers[lo] + numbers[hi]. If it equals target, return [lo + 1, hi + 1]. If it's less than target, advance lo; if greater, retreat hi. Repeat while lo < hi.

Why moving a pointer is provably safe. Suppose sum > target. Because the array is sorted, numbers[hi] is the largest value still in play. Pairing it with anything to its left gives a sum ≥ sum only if we picked a larger left value — but the smallest possible partner for numbers[hi] is numbers[lo], and even that overshoots. So numbers[hi] can never be part of a valid pair, and we can discard it forever by doing hi--. The symmetric argument holds for sum < target: numbers[lo] is too small to ever reach the target even paired with the maximum, so we drop it with lo++. Every step eliminates exactly one element that is provably useless — this elimination argument is the heart of the proof and what you should say aloud.

Why this beats the hash map here. Classic Two Sum uses O(n) extra space because the array is unsorted — you must remember what you've seen. Here the sorted order means each comparison already tells you which direction to go, so you carry no memory at all: two integer indices. The problem even mandates O(1) space, explicitly ruling the hash map out. Sorted input plus a target comparison is the canonical two-pointer setup.

Why `lo < hi` and not `lo <= hi`. The two numbers must occupy distinct positions. If we allowed lo == hi, we'd be adding one element to itself, which violates 'may not use the same element twice'. Stopping the moment the pointers meet guarantees index1 < index2 always holds.

Why the single-solution guarantee matters. Because exactly one pair works, the first equality we hit is the answer — no need to keep scanning. If the problem asked for all pairs, we'd skip past duplicates on both ends after recording a hit instead of returning.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numbers = [2, 7, 11, 15], target = 18

Array state

lo=0, hi=3

2 + 15 = 17 < 18 — too small, move lo right

lo ↓

[0]

[1]

[2]

hi ↓

[3]

Current pointerResolved stateNot processed

Final result[2, 3]

C · Code with teaching comments

solution.javaJava

Opposite-End Two Pointers (Optimal) — optimal

5 teaching notes

1
public int[] twoSum(int[] numbers, int target) {
2
    // Pointers at the smallest and largest values — the extremes of a sorted array.
3
    int lo = 0, hi = numbers.length - 1;
4
    // Strict < so the two indices stay distinct; stops when they meet.
5
    while (lo < hi) {
6
        int sum = numbers[lo] + numbers[hi];
7
        if (sum == target) {
8
            // 1-indexed output — the prompt requires positions added by one.
9
            return new int[]{lo + 1, hi + 1};
10
        // Sum too small → the smallest value is useless, advance lo to grow the sum.
11
        } else if (sum < target) {
12
            lo++;
13
        } else {
14
            // Sum too big → the largest value is useless, retreat hi to shrink the sum.
15
            hi--;
16
        }
17
    }
18
    return new int[]{-1, -1};
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The sign of (sum − target) is a compass: positive means 'too big, shrink from the right'; negative means 'too small, grow from the left'. Each comparison deletes one candidate permanently, so a quadratic pair search collapses into a single linear pass with zero extra memory. Internalize this and 3Sum, Container With Most Water, and Trapping Rain Water all become variations on the same converging-pointers idea.

ComplexityO(n) time, O(1) space — Each iteration moves lo right or hi left by one, so the pointers meet after at most n − 1 steps → O(n) time. Two integer indices only → O(1) space.

E · Edge cases and pitfalls7numbers = [-1, 0], target = -1 — lo=0, hi=1: -1 + 0 = -1 == target → return [1, 2]. Negatives need no special handling.Explore edge cases

Edge cases handled

numbers = [-1, 0], target = -1lo=0, hi=1: -1 + 0 = -1 == target → return [1, 2]. Negatives need no special handling.
numbers = [1, 2, 3, 4, 4, 9, 56, 90], target = 8Pointers converge to the 4+4 pair using two distinct duplicate positions → returns [4, 5]. lo < hi guarantees distinctness.
numbers = [5, 25, 75], target = 100lo=0,hi=2: 80<100 → lo++; lo=1,hi=2: 25+75=100 → return [2, 3].

Pitfalls

Returning [lo, hi] instead of [lo + 1, hi + 1] — the problem is 1-indexed.
Using lo <= hi — lets a single element pair with itself.
Moving the wrong pointer (e.g. lo-- when sum is too big) — the pointers never converge.
Reaching for a hash map and violating the O(1)-space requirement.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic 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) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

0-indexed instead of 1-indexed return

The prompt explicitly says the indices are 'added by one'. Returning the raw pointers fails every test even though the logic is correct.

Explore the code comparison

Don't write this

if (sum == target) {
    return new int[]{lo, hi};
}

Write this instead

if (sum == target) {
    return new int[]{lo + 1, hi + 1};
}

Moving the wrong pointer

If you advance lo when the sum is too big, you only make the sum larger — the pointers diverge and never find the answer.

Explore the code comparison

Don't write this

if s < target:
    hi -= 1
else:
    lo += 1

Write this instead

if s < target:
    lo += 1
else:
    hi -= 1

Reusing one element via lo <= hi

When lo == hi the loop adds numbers[lo] to itself, which can produce a false match and violates 'may not use the same element twice'.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Opposite-end two pointers on a sorted array

Code pattern to memorize

lo, hi = 0, n - 1
while lo < hi:
    s = nums[lo] + nums[hi]
    if s == target: return [lo + 1, hi + 1]   # 1-indexed!
    elif s < target: lo += 1   # need bigger → move left pointer right
    else: hi -= 1              # need smaller → move right pointer left

Rules to remember

1Return 1-indexed positions — [lo + 1, hi + 1]. This is the #1 wrong-answer on this exact problem.
2Sum too small → move lo right (toward larger values). Sum too big → move hi left (toward smaller values). Never both.
3Loop while lo < hi, never lo <= hi — equal pointers would reuse one element twice.
4The sorted order is the whole point — it makes each comparison tell you which pointer to move. Do not reach for a hash map here.
5No extra space, no sorting cost — the input is already sorted, so this is strictly better than Two Sum's hash map.

Use this pattern when

Array (or string) is **sorted** and you need a pair summing to a target
You want **O(1) space** — no room for a hash map
Each comparison can tell you which side to discard / advance
Monotonic structure: moving a pointer changes the sum predictably

Choose another pattern when

Array is **unsorted** and you need original indices → hash map (classic Two Sum)
Sorting would destroy a required index mapping → don't sort, use a hash map
You need **all** pairs, not one → fix-one + two-pointer (3Sum) or counting
Lookups aren't monotonic in a pointer's position → two pointers won't converge

Interview takeaway

When an array is sorted, opposite-end two pointers turn pair-finding into an O(n)/O(1) sweep: the sign of (sum − target) tells you exactly which pointer to move. This is the same engine inside 3Sum, Container With Most Water, and Trapping Rain Water.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical opposite-end Two Pointers on a sorted array. Recognise it whenever the input is sorted (or you can afford to sort) and each comparison tells you which side to discard. Same engine as 3Sum, Container With Most Water, and Trapping Rain Water.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two Sum
Unsorted version — sorted trick is gone, fall back to the hash-map complement lookup.
3Sum
Coming soon
Sort, fix one element, then run this exact two-pointer sweep on the rest. O(n²).
Container With Most Water
Same opposite-end pointers, but move the pointer at the shorter line to maximize area.
Two Sum IV — Input is a BST
Coming soon
In-order traversal gives a sorted stream; then the same two-pointer idea applies.

Same pattern

←

Move Zeroes

Continue · Next problem

Squares of a Sorted Array

mediumArraysLC #167Frequently asked

Two Sum II — Input Array Is Sorted

LCPractice

Two Pointers · 8 of 30 · 9 min

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

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2, where 1 ≤ index1 < index2 ≤ numbers.length.

The tests are generated such that there is **exactly one solution**. You may not use the same element twice. Your solution must use only constant extra space.

In plain English

Examples

Example 1

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Note: 2 + 7 = 9. Their 1-indexed positions are 1 and 2.

Example 2

Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]
Note: 2 + 4 = 6. Positions 1 and 3.

Example 3

Input: numbers = [-1, 0], target = -1
Output: [1, 2]
Note: -1 + 0 = -1. Negatives work with no special handling.

Constraints

2 ≤ numbers.length ≤ 3 × 10⁴
-1000 ≤ numbers[i] ≤ 1000
numbers is sorted in non-decreasing order
-1000 ≤ target ≤ 1000
Exactly one valid answer exists
Must use O(1) extra space

Clarifying questions4First question: Is the array guaranteed sorted, and in which order?Explore questions

Q1.Is the array guaranteed sorted, and in which order?
Yes — non-decreasing. That precondition is the entire reason two pointers works; without it you'd be back to a hash map.
Q2.Are the returned indices 0-indexed or 1-indexed?
1-indexed. The prompt says 'added by one'. Returning [lo, hi] instead of [lo + 1, hi + 1] is the most common silent failure.
Q3.Is there always exactly one solution?
Yes. So I can return immediately on the first matching pair without worrying about ties.
Q4.Can the values be negative or duplicated?
Both. Negatives are fine — the comparison logic doesn't assume positivity. Duplicates are fine too because lo < hi guarantees two distinct positions.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit the 'sorted' precondition instead of blindly reusing the Two Sum hash map. The whole problem is a one-word change ('sorted') that should change your entire approach.

Where candidates slip

Returning 0-indexed answers (the prompt demands 1-indexed), or reaching for a hash map and throwing away the O(1)-space win the sorted input hands you for free.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Nested Pair Scan	`O(n²)`	`O(1)`	Mention briefly to anchor the progression, then immediately note it ignores the 'sorted' gift and is strictly worse.	Read
2	Opposite-End Two Pointers (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Lead with 'because it's sorted' — that justification is the whole point of the medium rating.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Nested Pair Scan

TimeO(n²)SpaceO(1)

Mention briefly to anchor the progression, then immediately note it ignores the 'sorted' gift and is strictly worse.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the sorted property for a moment. What's the most literal way to find a pair that sums to target?

2Hint 2Explore hint

Try every pair (i, j) with j > i and test numbers[i] + numbers[j] == target.

3Hint 3Explore hint

Two nested loops; return [i + 1, j + 1] on the first match. Note: this wastes the sorted order entirely.

A · Core idea

The mechanical translation of the prompt: fix the first index i, sweep every later index j, and check whether the two values add to target. Return the 1-indexed pair on the first hit.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numbers = [2, 7, 11, 15], target = 9

i=0, j=1

2 + 7 = 9

Statematch → return [1, 2]

Final result[1, 2]

C · Code with teaching comments

solution.javaJava

Brute Force — Nested Pair Scan — reference

2 teaching notes

1
public int[] twoSum(int[] numbers, int target) {
2
    for (int i = 0; i < numbers.length; i++) {
3
        // j starts at i+1 to avoid self-pairing and rechecking reversed pairs.
4
        for (int j = i + 1; j < numbers.length; j++) {
5
            if (numbers[i] + numbers[j] == target) {
6
                // 1-indexed output — add one to each position.
7
                return new int[]{i + 1, j + 1};
8
            }
9
        }
10
    }
11
    return new int[]{-1, -1};
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — n(n−1)/2 ≈ n²/2 comparisons in the worst case; no extra data structures, so O(1) space.

E · Edge cases and pitfalls3Returning [i, j] instead of [i + 1, j + 1] — this problem is 1-indexed.Explore edge cases

Pitfalls

Returning [i, j] instead of [i + 1, j + 1] — this problem is 1-indexed.
Ignoring the 'sorted' precondition entirely — the signal that a better answer exists.
Starting j at 0 — reuses an element with itself.

03.2

Approach 2 of 2 · Optimal

Opposite-End Two Pointers (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Lead with 'because it's sorted' — that justification is the whole point of the medium rating.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array is sorted. If you stand one pointer at the smallest value and one at the largest, what does their sum tell you about which value to swap out?

2Hint 2Explore hint

If the sum is too big, the only way to shrink it without losing reachable pairs is to move the right pointer left. If it's too small, move the left pointer right.

3Hint 3Explore hint

Loop while lo < hi. On equality return [lo + 1, hi + 1]. Each step discards exactly one element that can't be part of any answer — that's why it's O(n).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numbers = [2, 7, 11, 15], target = 18

Array state

lo=0, hi=3

2 + 15 = 17 < 18 — too small, move lo right

lo ↓

[0]

[1]

[2]

hi ↓

[3]

Current pointerResolved stateNot processed

Final result[2, 3]

C · Code with teaching comments

solution.javaJava

Opposite-End Two Pointers (Optimal) — optimal

5 teaching notes

1
public int[] twoSum(int[] numbers, int target) {
2
    // Pointers at the smallest and largest values — the extremes of a sorted array.
3
    int lo = 0, hi = numbers.length - 1;
4
    // Strict < so the two indices stay distinct; stops when they meet.
5
    while (lo < hi) {
6
        int sum = numbers[lo] + numbers[hi];
7
        if (sum == target) {
8
            // 1-indexed output — the prompt requires positions added by one.
9
            return new int[]{lo + 1, hi + 1};
10
        // Sum too small → the smallest value is useless, advance lo to grow the sum.
11
        } else if (sum < target) {
12
            lo++;
13
        } else {
14
            // Sum too big → the largest value is useless, retreat hi to shrink the sum.
15
            hi--;
16
        }
17
    }
18
    return new int[]{-1, -1};
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Each iteration moves lo right or hi left by one, so the pointers meet after at most n − 1 steps → O(n) time. Two integer indices only → O(1) space.

E · Edge cases and pitfalls7numbers = [-1, 0], target = -1 — lo=0, hi=1: -1 + 0 = -1 == target → return [1, 2]. Negatives need no special handling.Explore edge cases

Edge cases handled

numbers = [-1, 0], target = -1lo=0, hi=1: -1 + 0 = -1 == target → return [1, 2]. Negatives need no special handling.
numbers = [1, 2, 3, 4, 4, 9, 56, 90], target = 8Pointers converge to the 4+4 pair using two distinct duplicate positions → returns [4, 5]. lo < hi guarantees distinctness.
numbers = [5, 25, 75], target = 100lo=0,hi=2: 80<100 → lo++; lo=1,hi=2: 25+75=100 → return [2, 3].

Pitfalls

Returning [lo, hi] instead of [lo + 1, hi + 1] — the problem is 1-indexed.
Using lo <= hi — lets a single element pair with itself.
Moving the wrong pointer (e.g. lo-- when sum is too big) — the pointers never converge.
Reaching for a hash map and violating the O(1)-space requirement.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

0-indexed instead of 1-indexed return

The prompt explicitly says the indices are 'added by one'. Returning the raw pointers fails every test even though the logic is correct.

Explore the code comparison

Don't write this

if (sum == target) {
    return new int[]{lo, hi};
}

Write this instead

if (sum == target) {
    return new int[]{lo + 1, hi + 1};
}

Moving the wrong pointer

If you advance lo when the sum is too big, you only make the sum larger — the pointers diverge and never find the answer.

Explore the code comparison

Don't write this

if s < target:
    hi -= 1
else:
    lo += 1

Write this instead

if s < target:
    lo += 1
else:
    hi -= 1

Reusing one element via lo <= hi

When lo == hi the loop adds numbers[lo] to itself, which can produce a false match and violates 'may not use the same element twice'.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Opposite-end two pointers on a sorted array

Code pattern to memorize

lo, hi = 0, n - 1
while lo < hi:
    s = nums[lo] + nums[hi]
    if s == target: return [lo + 1, hi + 1]   # 1-indexed!
    elif s < target: lo += 1   # need bigger → move left pointer right
    else: hi -= 1              # need smaller → move right pointer left

Rules to remember

1Return 1-indexed positions — [lo + 1, hi + 1]. This is the #1 wrong-answer on this exact problem.
2Sum too small → move lo right (toward larger values). Sum too big → move hi left (toward smaller values). Never both.
3Loop while lo < hi, never lo <= hi — equal pointers would reuse one element twice.
4The sorted order is the whole point — it makes each comparison tell you which pointer to move. Do not reach for a hash map here.
5No extra space, no sorting cost — the input is already sorted, so this is strictly better than Two Sum's hash map.

Use this pattern when

Array (or string) is **sorted** and you need a pair summing to a target
You want **O(1) space** — no room for a hash map
Each comparison can tell you which side to discard / advance
Monotonic structure: moving a pointer changes the sum predictably

Choose another pattern when

Array is **unsorted** and you need original indices → hash map (classic Two Sum)
Sorting would destroy a required index mapping → don't sort, use a hash map
You need **all** pairs, not one → fix-one + two-pointer (3Sum) or counting
Lookups aren't monotonic in a pointer's position → two pointers won't converge

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two Sum
Unsorted version — sorted trick is gone, fall back to the hash-map complement lookup.
3Sum
Coming soon
Sort, fix one element, then run this exact two-pointer sweep on the rest. O(n²).
Container With Most Water
Same opposite-end pointers, but move the pointer at the shorter line to maximize area.
Two Sum IV — Input is a BST
Coming soon
In-order traversal gives a sorted stream; then the same two-pointer idea applies.

Same pattern

←

Move Zeroes

Continue · Next problem

Squares of a Sorted Array