Two Sum II — How Sorted Order Changed My Two-Pointer Approach
LeetCode 167: compare the first idea with the accepted strategy, then use sorted order to explain every pointer move.
- Platform
- LeetCode
- Problem number
- 167
- Problem difficulty
- Medium
- Pattern
- Two Pointers — Opposite Direction
- Solution language
- Python 3
Choose your starting pointSee why my first idea fails · Try the examples · Read the correctness proof
The key question is not simply which pointer moves. It is: what evidence lets me rule out an endpoint without losing the answer?
The problem in one minute
Given a list of integers that is already sorted in non-decreasing order, find two different positions whose values add to a target. Return their one-based positions. The official inputs have exactly one valid pair, and the solution must use constant extra space.
numbers = [1, 3, 6, 10, 14]
target = 13
# Values: 3 + 10 = 13
# Indices: 1 and 3 in Python
# Return: [2, 4] in the problem’s one-based numberingThe list is not changed. Equal values may appear at different positions, but the same position cannot be used twice. Full constraints and the original statement are available at the official link above.
Watch the reasoning change
My first idea kept i at the first element and moved j forward. The accepted solution started at opposite ends and let either pointer move. Both animations below use the same five numbers and target 13. Use Next step to compare their decisions, or play them at a comfortable speed.
Pause and predictWhen 1 + 14 is too large, which endpoint can be ruled out? Try to justify the move before advancing the accepted trace.
Same input, two strategies
My initial attempt
[1,3,6,10,14]; target 13. Exactly one valid pair.
i = 0; j = 1— i=0, j=1. Keep i on the first number and scan j forward. This is the initial idea being tested, not the accepted algorithm.sum < target— i=0, j=1. 1 + 3 = 4, below 13. My initial idea was to increase j while leaving i fixed.j += 1; i stays at 0— i=0, j=2. Move j to index 2. The next comparison will use 1 and 6.sum < target— i=0, j=2. 1 + 6 = 7, below 13. My initial idea was to increase j while leaving i fixed.j += 1; i stays at 0— i=0, j=3. Move j to index 3. The next comparison will use 1 and 10.sum < target— i=0, j=3. 1 + 10 = 11, below 13. My initial idea was to increase j while leaving i fixed.j += 1; i stays at 0— i=0, j=4. Move j to index 4. The next comparison will use 1 and 14.sum > target: initial attempt stops— i=0, j=4. 1 + 14 = 15, above 13. This fixed-i scan stops here. It misses an existing pair: positions [2, 4].
Initial attempt stopped without finding a pair; this is an incomplete strategy.
Accepted two pointers
[1,3,6,10,14]; target 13. Exactly one valid pair.
i = 0; j = len(numbers) - 1— i=0, j=4. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] > target— i=0, j=4. 1 + 14 = 15, above 13. Even the smallest remaining value is too large with 14, so no remaining pair using index 4 can work.j -= 1— i=0, j=3. Rule out index 4 and move j left to 3. Evaluate the new pair next.numbers[i] + numbers[j] < target— i=0, j=3. 1 + 10 = 11, below 13. Even the largest remaining partner cannot make 1 reach the target, so no remaining pair using index 0 can work.i += 1— i=1, j=3. Rule out index 0 and move i right to 1. Evaluate the new pair next.numbers[i] + numbers[j] == target— i=1, j=3. 3 + 10 = 13. This matches 13; the indices are different because i < j.return [i + 1, j + 1]— i=1, j=3. Return [2, 4]. These are one-based positions, not the values 3 and 10.
Returned indices: [2, 4].
The first scan jumps from 1 + 10 = 11 to 1 + 14 = 15, then stops. That does not mean the whole problem has no answer: 3 + 10 = 13 is still available. The accepted strategy can reach that pair because i is allowed to move too.
How I Arrived at the Solution
Stage 1 — Starting with combinations
I began by thinking about how many distinct pairs an array could contain. For four elements, I initially mixed up permutations and combinations, then corrected the count to C(4, 2) = 6. A pair of positions is unordered here: checking positions 0 and 1 is the same candidate as checking 1 and 0.
Four positions | The six distinct pairs |
|---|---|
0, 1, 2, 3 | (0,1), (0,2), (0,3), (1,2), (1,3), (2,3) |
For n positions, there are n(n − 1) / 2 pairs. That is quadratic work if I enumerate all of them. The more useful question was whether the sorted input could help me eliminate candidates rather than visit each pair individually.
Stage 2 — My first pointer approach
My initial starting positions were i = 0 and j = 1. If the sum was too small, I considered increasing j. I also noticed a correct boundary fact: if the two smallest values already exceed the target, no pair in a sorted array can work.
But that boundary fact did not make the rest of my strategy complete. On my counterexample, keeping i fixed produced the following sums:
i | j | Sum | Compared with target 13 |
|---|---|---|---|
0 | 1 | 1 + 3 = 4 | Too small |
0 | 2 | 1 + 6 = 7 | Too small |
0 | 3 | 1 + 10 = 11 | Too small |
0 | 4 | 1 + 14 = 15 | Too large |
The sum crossed the target without finding it, even though positions 1 and 3 contain 3 and 10. I had only explored the pairs containing the first element. This counterexample invalidated the fixed-i scan as a complete algorithm; it did not invalidate two pointers as a technique.
Stage 3 — Considering binary search
Since the array was sorted, I next considered binary search. I explored the idea of dividing it into two halves and initially thought that the answer might need one number from each half. That was an unnecessary restriction: the pair can be entirely within one half.
numbers = [1, 2, 3, 10, 11, 12]
target = 5
# 2 + 3 = 5: both values are in the left half.I also clarified that binary search normally changes low and high index boundaries; it does not need to copy or physically split the array. A valid alternative is to fix each index i and binary-search the suffix after i for target − numbers[i]. Searching only after i keeps the positions distinct.
That alternative takes O(n log n) time and can use O(1) auxiliary space with an iterative search over indices. Binary search was an approach I considered, not the final code I submitted.
Stage 4 — Starting at opposite ends
I reconsidered the starting positions: i = 0 and j = len(numbers) − 1. Now the current pair spans the smallest and largest values still under consideration. The sorted order can tell me which endpoint is impossible to use.
If the sum is too large, decrement j.
If the sum is too small, increment i.
If it equals the target, return [i + 1, j + 1].
This was the opposite-end strategy I independently derived and implemented. The important improvement was a reason for each elimination, rather than a direction that merely seemed likely to help.
Handwritten reasoning for Two Sum II — image to be addedReserved for the original handwritten reasoning for this problem. The written reasoning and submission record are included in this note.
Stage 5 — Understanding the complexity
At first, the narrowing interval reminded me of binary search, so I thought the complexity might be O(log n). The distinction became clearer when I looked at how much was removed each time. Binary search removes approximately half the remaining interval. My loop moves one boundary by one position.
The distance j − i starts at n − 1 and decreases by one whenever a pointer moves. There can be at most n − 1 loop iterations before a match or before the pointers meet. This is O(n) time with O(1) auxiliary space.
My original accepted Python implementation
This is my submitted implementation. It repeats the addition in the two conditions; the separate refinement below only removes that repetition.
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
i = 0
j = len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] > target:
j -= 1
elif numbers[i] + numbers[j] < target:
i += 1
else:
return [i + 1, j + 1]Read the code one decision at a time
Line or expression | What it means |
|---|---|
i = 0 | Start at the smallest value in the full candidate interval. |
j = len(numbers) − 1 | Start at the largest value, using the last valid Python index. |
while i < j | Only consider pairs of different positions. Meeting or crossing ends the search. |
sum > target: j -= 1 | The right endpoint cannot work with any remaining partner. Remove it. |
sum < target: i += 1 | The left endpoint cannot work with any remaining partner. Remove it. |
return [i + 1, j + 1] | Convert zero-based Python indices to the required one-based positions. Return indices, not the values. |
Optional refinement: compute the sum once
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
i = 0
j = len(numbers) - 1
while i < j:
current_sum = numbers[i] + numbers[j]
if current_sum > target:
j -= 1
elif current_sum < target:
i += 1
else:
return [i + 1, j + 1]This uses the same decisions and asymptotic complexity. Under the official unique-solution guarantee, the loop finds a pair and returns it. On a custom input with no solution, this exact function falls through and returns None; the explorer labels that situation explicitly.
Try the examples
Start with the standard case, then try negatives, duplicates and the two-element boundary. Before advancing, predict the next move. The last example brings the pointers close together; the multiple-pair example deliberately shows a limit of the problem’s input guarantee.
Worked examples
A · Start simple
The sum is too large twice, so j moves left twice. The values 2 and 7 then match.
Accepted two pointers
[2,7,11,15]; target 9. Exactly one valid pair.
i = 0; j = len(numbers) - 1— i=0, j=3. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] > target— i=0, j=3. 2 + 15 = 17, above 9. Even the smallest remaining value is too large with 15, so no remaining pair using index 3 can work.j -= 1— i=0, j=2. Rule out index 3 and move j left to 2. Evaluate the new pair next.numbers[i] + numbers[j] > target— i=0, j=2. 2 + 11 = 13, above 9. Even the smallest remaining value is too large with 11, so no remaining pair using index 2 can work.j -= 1— i=0, j=1. Rule out index 2 and move j left to 1. Evaluate the new pair next.numbers[i] + numbers[j] == target— i=0, j=1. 2 + 7 = 9. This matches 9; the indices are different because i < j.return [i + 1, j + 1]— i=0, j=1. Return [1, 2]. These are one-based positions, not the values 2 and 7.
Returned indices: [1, 2].
B · The breakthrough
Both endpoints must be able to move. The valid pair is 3 and 10, not a pair containing the first number.
Accepted two pointers
[1,3,6,10,14]; target 13. Exactly one valid pair.
i = 0; j = len(numbers) - 1— i=0, j=4. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] > target— i=0, j=4. 1 + 14 = 15, above 13. Even the smallest remaining value is too large with 14, so no remaining pair using index 4 can work.j -= 1— i=0, j=3. Rule out index 4 and move j left to 3. Evaluate the new pair next.numbers[i] + numbers[j] < target— i=0, j=3. 1 + 10 = 11, below 13. Even the largest remaining partner cannot make 1 reach the target, so no remaining pair using index 0 can work.i += 1— i=1, j=3. Rule out index 0 and move i right to 1. Evaluate the new pair next.numbers[i] + numbers[j] == target— i=1, j=3. 3 + 10 = 13. This matches 13; the indices are different because i < j.return [i + 1, j + 1]— i=1, j=3. Return [2, 4]. These are one-based positions, not the values 3 and 10.
Returned indices: [2, 4].
C · Negative numbers
−8 + 9 already equals 1. The proof uses sorted order, so negative numbers need no special branch.
Accepted two pointers
[-8,-3,1,4,9]; target 1. Multiple valid pairs; outside the unique-solution guarantee.
i = 0; j = len(numbers) - 1— i=0, j=4. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] == target— i=0, j=4. -8 + 9 = 1. This matches 1; the indices are different because i < j.return [i + 1, j + 1]— i=0, j=4. Return [1, 5]. These are one-based positions, not the values -8 and 9.
Returned indices: [1, 5].
D · Equal values, distinct indices
The two 2s occupy different positions. Returning [2, 3] uses two elements, not one element twice.
Accepted two pointers
[1,2,2,4,6]; target 4. Exactly one valid pair.
i = 0; j = len(numbers) - 1— i=0, j=4. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] > target— i=0, j=4. 1 + 6 = 7, above 4. Even the smallest remaining value is too large with 6, so no remaining pair using index 4 can work.j -= 1— i=0, j=3. Rule out index 4 and move j left to 3. Evaluate the new pair next.numbers[i] + numbers[j] > target— i=0, j=3. 1 + 4 = 5, above 4. Even the smallest remaining value is too large with 4, so no remaining pair using index 3 can work.j -= 1— i=0, j=2. Rule out index 3 and move j left to 2. Evaluate the new pair next.numbers[i] + numbers[j] < target— i=0, j=2. 1 + 2 = 3, below 4. Even the largest remaining partner cannot make 1 reach the target, so no remaining pair using index 0 can work.i += 1— i=1, j=2. Rule out index 0 and move i right to 1. Evaluate the new pair next.numbers[i] + numbers[j] == target— i=1, j=2. 2 + 2 = 4. This matches 4; the indices are different because i < j.return [i + 1, j + 1]— i=1, j=2. Return [2, 3]. These are one-based positions, not the values 2 and 2.
Returned indices: [2, 3].
E · Just two elements
There is only one candidate pair. The very first comparison finds it.
Accepted two pointers
[-1,0]; target -1. Exactly one valid pair.
i = 0; j = len(numbers) - 1— i=0, j=1. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] == target— i=0, j=1. -1 + 0 = -1. This matches -1; the indices are different because i < j.return [i + 1, j + 1]— i=0, j=1. Return [1, 2]. These are one-based positions, not the values -1 and 0.
Returned indices: [1, 2].
F · More than one valid pair
This supplied example has two valid pairs: 2 + 8 and 4 + 6. It is a useful custom case, but does not meet LeetCode’s unique-solution guarantee.
Accepted two pointers
[1,2,4,6,8,11]; target 10. Multiple valid pairs; outside the unique-solution guarantee.
i = 0; j = len(numbers) - 1— i=0, j=5. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] > target— i=0, j=5. 1 + 11 = 12, above 10. Even the smallest remaining value is too large with 11, so no remaining pair using index 5 can work.j -= 1— i=0, j=4. Rule out index 5 and move j left to 4. Evaluate the new pair next.numbers[i] + numbers[j] < target— i=0, j=4. 1 + 8 = 9, below 10. Even the largest remaining partner cannot make 1 reach the target, so no remaining pair using index 0 can work.i += 1— i=1, j=4. Rule out index 0 and move i right to 1. Evaluate the new pair next.numbers[i] + numbers[j] == target— i=1, j=4. 2 + 8 = 10. This matches 10; the indices are different because i < j.return [i + 1, j + 1]— i=1, j=4. Return [2, 5]. These are one-based positions, not the values 2 and 8.
Returned indices: [2, 5].
G · Almost meeting
Five comparisons bring the pointers to adjacent indices. They find 3 + 4 before meeting; the same element is never reused.
Accepted two pointers
[1,2,3,4,8,14]; target 7. Exactly one valid pair.
i = 0; j = len(numbers) - 1— i=0, j=5. Start at opposite ends. Sorted order will tell us which endpoint can be ruled out.numbers[i] + numbers[j] > target— i=0, j=5. 1 + 14 = 15, above 7. Even the smallest remaining value is too large with 14, so no remaining pair using index 5 can work.j -= 1— i=0, j=4. Rule out index 5 and move j left to 4. Evaluate the new pair next.numbers[i] + numbers[j] > target— i=0, j=4. 1 + 8 = 9, above 7. Even the smallest remaining value is too large with 8, so no remaining pair using index 4 can work.j -= 1— i=0, j=3. Rule out index 4 and move j left to 3. Evaluate the new pair next.numbers[i] + numbers[j] < target— i=0, j=3. 1 + 4 = 5, below 7. Even the largest remaining partner cannot make 1 reach the target, so no remaining pair using index 0 can work.i += 1— i=1, j=3. Rule out index 0 and move i right to 1. Evaluate the new pair next.numbers[i] + numbers[j] < target— i=1, j=3. 2 + 4 = 6, below 7. Even the largest remaining partner cannot make 2 reach the target, so no remaining pair using index 1 can work.i += 1— i=2, j=3. Rule out index 1 and move i right to 2. Evaluate the new pair next.numbers[i] + numbers[j] == target— i=2, j=3. 3 + 4 = 7. This matches 7; the indices are different because i < j.return [i + 1, j + 1]— i=2, j=3. Return [3, 4]. These are one-based positions, not the values 3 and 4.
Returned indices: [3, 4].
A correction to the supplied example FFor [1, 2, 4, 6, 8, 11] and target 10, both 2 + 8 and 4 + 6 work. The opposite-end algorithm returns [2, 5], but [3, 4] is also valid. The explorer labels both index pairs; this input must not be described as having exactly one solution.
Why the elimination is safe
Why sorted order is essential
Inside the current interval, numbers[i] is the smallest remaining value and numbers[j] is the largest. Those two facts are what turn a comparison of one pair into a conclusion about a whole row of candidate pairs. Without sorted order, the same pointer moves could discard the answer.
If the sum is too large, discard the right endpoint
Suppose numbers[i] + numbers[j] > target. For any remaining index k between i and j − 1, numbers[k] ≥ numbers[i]. Therefore numbers[k] + numbers[j] ≥ numbers[i] + numbers[j] > target. No valid pair in the remaining interval can use j, so moving j left is safe.
If the sum is too small, discard the left endpoint
Suppose numbers[i] + numbers[j] < target. For any remaining index k between i + 1 and j, numbers[k] ≤ numbers[j]. Therefore numbers[i] + numbers[k] ≤ numbers[i] + numbers[j] < target. No valid pair can use i, so moving i right is safe.
Invariant, termination and correctness
Initially the candidate interval contains every position, so it contains the guaranteed solution.
Invariant: if a valid pair exists, a valid pair remains entirely inside [i, j]. Every removed endpoint has been proved unusable.
A matching sum immediately gives a valid pair of distinct positions because i < j.
Otherwise one endpoint is safely removed. The invariant is preserved and j − i decreases by one.
The loop cannot continue indefinitely. The guaranteed solution cannot be discarded, so an official valid input must produce a match before the interval loses its last distinct pair.
The condition i < j also prevents returning the same element twice. Duplicate values are fine: two 2s at different positions are different elements. A single 2 at one position cannot supply both numbers.
Complexity: narrowing is not always halving
Approach | Time | How it searches |
|---|---|---|
Every distinct pair | O(n²) | Enumerates n(n − 1) / 2 candidates. |
Binary search for each complement | O(n log n) | Runs a logarithmic suffix search for each fixed position. |
Accepted opposite-end pointers | O(n) | Removes one impossible endpoint per pointer move. |
The submitted algorithm only stores i and j; the refinement also stores one current sum. These are fixed-size values, so auxiliary space is O(1). It reads the input list directly and does not make slices, copy halves, or allocate a lookup table.
The O(1) space claim describes the Python solution. The teaching animation keeps snapshots so you can rewind; those snapshots are separate from the submitted algorithm.
Growth models at n = 64
Mathematical models, not measured runtimes. With JavaScript, choose other input sizes.
| Model | Approximate growth |
|---|---|
| O(log n) | 6 |
| O(n) | 64 |
| O(n log n) | 384 |
| O(n²) | 4096 |
The pointer-distance view inside the example explorer shows actual movement for the selected input. It is a different kind of evidence from these growth models: a concrete trace rather than an asymptotic estimate.
Common mistakes and debugging strategies
Mistake | A better check |
|---|---|
Moving the wrong endpoint | State the inequality that proves an endpoint impossible before changing it. |
Keeping i fixed | Test [1, 3, 6, 10, 14] with target 13. The valid pair excludes the first element. |
Calling this O(log n) | Track j − i. A one-position decrease is not the same as halving the interval. |
Returning the values or zero-based indices | For the counterexample, values [3, 10] correspond to the required indices [2, 4]. |
Allowing i == j | A matching sum made from one cell twice is not a valid pair. |
Forgetting a pointer update | Check that every non-matching iteration makes the interval smaller. |
Applying the moves to unsorted data | The endpoint inequalities no longer hold. Do not silently sort if the required original indices would then be lost. |
When this technique does not apply directly
The submitted strategy depends on sorted values and a target-sum comparison. For unsorted inputs, a different approach or additional handling of original indices is needed. A problem asking for every pair, all value combinations, or a count of pairs also needs different duplicate and output handling. A solution to this one guaranteed-pair problem should not be reused unchanged for those contracts.
Implementation and Result
Submission record supplied for this learning note, dated 17 November 2026:
Field | Recorded result |
|---|---|
Language | Python 3 |
Status | Accepted |
Test cases | 26 / 26 passed |
Runtime | 6 ms |
Memory | 22.55 MB |
Accepted Two Sum II submission — image to be addedReserved for the original accepted submission screenshot. The written reasoning and submission record are included in this note.
These are the supplied submission figures, not measurements of the browser animation. Runtime and memory can vary between runs and environments; the correctness argument and asymptotic analysis explain the choice of algorithm.
What I learned
My first idea was incomplete, but it gave me a concrete counterexample to investigate. Considering binary search helped me separate “the input is sorted” from “this must be binary search”. The final improvement was understanding what sorted order allowed me to rule out.
The lesson I want to carry forward is to justify elimination. Moving a pointer is useful only when I can explain why the candidates being removed cannot contain the answer.