Two Sum II - Input Array Is Sorted (LeetCode 167)
You're given numbers, a 1-indexed array of integers already sorted in non-decreasing order, plus a target value. Locate two distinct positions index_1 < index_2 whose values add up to target.
Return those two positions, 1-indexed, as [index_1, index_2].
Exactly one valid pair is guaranteed to exist, and you can't reuse the same element twice.
Do this using only constant extra space.
Worked Examples
numbers = [2,7,11,15], target = 9[1,2]numbers = [2,3,4], target = 6[1,3]numbers = [-1,0], target = -1[1,2]⚖️Formal Constraints & Bounds
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order.-1000 <= target <= 1000The tests are generated such that there is exactly one solution.
Core Insight
Sortedness gives monotonicity: sum > target proves right element is too big for any valid pair; sum < target proves left element is too small.
Real-World Scenario & Production Applications
Financial portfolio pair matching and hardware bus packet alignment across memory banks.
Subproblems & Recurrence Decomposition3 Phases
Because the input is already sorted, start pointers at both extremes: left = 0, right = len(numbers) - 1.
left, right = 0, len(numbers) - 1Step-by-Step Execution Trace Table
| Step | Pointers (left, right) | Current Sum | Comparison vs target = 9 | Elimination Decision | New (left, right) |
|---|---|---|---|---|---|
| 1 | (0, 5) | 1 + 11 = 12 | 12 > 9 (Too big) | 11 is too large for any partner discard right end (right = 4) | (0, 4) |
| 2 | (0, 4) | 1 + 7 = 8 | 8 < 9 (Too small) | 1 is too small for any partner discard left end (left = 1) | (1, 4) |
| 3 | (1, 4) | 3 + 7 = 10 | 10 > 9 (Too big) | Discard right end (right = 3) | (1, 3) |
| 4 | (1, 3) | 3 + 5 = 8 | 8 < 9 (Too small) | Discard left end (left = 2) | (2, 3) |
| 5 | (2, 3) | 4 + 5 = 9 | 9 == 9 (Exact Match) | Target reached! Return 1-indexed [2+1, 3+1] [3, 4] | — |
| 1 | left, right = 0, len(numbers) - 1 |
| 2 | while left < right: |
| 3 | curr_sum = numbers[left] + numbers[right] |
| 4 | if curr_sum == target: |
| 5 | return [left + 1, right + 1] |
| 6 | elif curr_sum < target: |
| 7 | left += 1 |
| 8 | else: |
| 9 | right -= 1 |
| 10 | return [] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Discarding an entire endpoint after a single comparison feels risky — how do you know you're not throwing away the answer? Sortedness is what makes it provably safe.
⚖️ The Analogy: A Seesaw You Can Only Push From the Ends
Picture the smallest and largest numbers sitting on opposite ends of a seesaw. If their combined sum is too big, the only way to bring it down is to swap out the larger end for something smaller — so you move the right pointer inward. If the sum is too small, the only way to raise it is to swap out the smaller end for something bigger — so you move the left pointer inward. Because the array is sorted, moving a pointer inward is the only direction that can fix an over/under-shoot; moving it the other way would only make the imbalance worse.
🔑 The Key Idea in the Code
Every element you discard when you move a pointer is provably eliminated: if numbers[left] + numbers[right] > target, then numbers[left] + numbers[anything smaller than right] is also too big, since the array is sorted — so skipping every intermediate right value is completely safe.
1-based indexing on the return value: LC 167 requires the 1-indexed positions
[left + 1, right + 1], not the raw 0-indexedleft/right; returning 0-indexed positions passes every trace by eye but fails the judge.Moving both pointers after a mismatch: only the pointer the comparison rules out may move; moving both skips pairs, so
numbers = [1, 2, 4, 6],target = 8never checks2 + 6.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array + find the pair that adds up to target, answered as 1-indexed positions, with only O(1) extra space: squeeze from both ends (Converging Pointers).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every pair that uses an index outside [left, right] cannot sum to target; one comparison of numbers[left] + numbers[right] with target rules out one more index.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Unsorted input: moving a pointer no longer raises or lowers the sum, so the squeeze can walk past the answer; the array must be sorted (LC 167 promises it).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Converging Pointers: left starts at index 0 and right at the last index. Because numbers is sorted, if the sum is smaller than target, numbers[left] is already paired with the largest value still available, so it can never reach target and I move left forward. If the sum is too big, numbers[right] is already paired with the smallest value still available, so I move right back. Each step rules out one element for good, which is why the pair can never be skipped. The trap is input that is not sorted: then moving a pointer no longer raises or lowers the sum, so the squeeze can walk past the answer. For unsorted input I would use a hash map, or sort value and index pairs to keep the original positions. Here the input is sorted and 1-indexed, so I return left + 1 and right + 1. It's
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the while loop: while left < right:. In each iteration, we evaluate current_sum = numbers[left] + numbers[right]. If the sum is too small, we increment left += 1; if too large, we decrement right -= 1. Because the distance (right - left) strictly decreases by 1 on every step, the loop executes at most N-1 times with O(1) arithmetic per step, yielding strictly O(N) time.
O(1) Auxiliary
Look at memory allocation: The search is iterative with O(1) call stack frames. We only store two scalar pointer variables (left, right) and one scalar sum accumulator. Auxiliary space is strictly O(1) in-place.
∑ (delta L + delta R) ≤ N ⟹ O(N)
Derivation Progression
(right - left) decreases by 1 each step
Sorted order guarantees that adjusting left rightward increases the sum and adjusting right leftward decreases the sum.
O(1) Arithmetic Per StepO(1) sum check
Testing current_sum == target takes constant time with zero inner loops.
N - 1 maximum steps ⟹ O(N)
The pointers converge from opposite ends, inspecting at most N elements before finding the pair.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(1) Only scalar pointers (left, right) in CPU registers
O(1) Returns 2-element index list
Boundary Best / Worst Cases
if outer pair sums to target.
.
when pair is in the middle.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "array is already sorted in non-decreasing order", "find two numbers that add up to target", "O(1) extra space". Converging opposite-direction pointers exploiting monotonic ordering.
. Time budget strictly , space strictly .
Values stay within , so the sum cannot overflow here.
Two Sum II - Input Array Is Sorted (LeetCode 167)
You're given numbers, a 1-indexed array of integers already sorted in non-decreasing order, plus a target value. Locate two distinct positions index_1 < index_2 whose values add up to target.
Return those two positions, 1-indexed, as [index_1, index_2].
Exactly one valid pair is guaranteed to exist, and you can't reuse the same element twice.
Do this using only constant extra space.
Worked Examples
numbers = [2,7,11,15], target = 9[1,2]numbers = [2,3,4], target = 6[1,3]numbers = [-1,0], target = -1[1,2]⚖️Formal Constraints & Bounds
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order.-1000 <= target <= 1000The tests are generated such that there is exactly one solution.
Core Insight
Sortedness gives monotonicity: sum > target proves right element is too big for any valid pair; sum < target proves left element is too small.
Real-World Scenario & Production Applications
Financial portfolio pair matching and hardware bus packet alignment across memory banks.
Subproblems & Recurrence Decomposition3 Phases
Because the input is already sorted, start pointers at both extremes: left = 0, right = len(numbers) - 1.
left, right = 0, len(numbers) - 1Step-by-Step Execution Trace Table
| Step | Pointers (left, right) | Current Sum | Comparison vs target = 9 | Elimination Decision | New (left, right) |
|---|---|---|---|---|---|
| 1 | (0, 5) | 1 + 11 = 12 | 12 > 9 (Too big) | 11 is too large for any partner discard right end (right = 4) | (0, 4) |
| 2 | (0, 4) | 1 + 7 = 8 | 8 < 9 (Too small) | 1 is too small for any partner discard left end (left = 1) | (1, 4) |
| 3 | (1, 4) | 3 + 7 = 10 | 10 > 9 (Too big) | Discard right end (right = 3) | (1, 3) |
| 4 | (1, 3) | 3 + 5 = 8 | 8 < 9 (Too small) | Discard left end (left = 2) | (2, 3) |
| 5 | (2, 3) | 4 + 5 = 9 | 9 == 9 (Exact Match) | Target reached! Return 1-indexed [2+1, 3+1] [3, 4] | — |
| 1 | left, right = 0, len(numbers) - 1 |
| 2 | while left < right: |
| 3 | curr_sum = numbers[left] + numbers[right] |
| 4 | if curr_sum == target: |
| 5 | return [left + 1, right + 1] |
| 6 | elif curr_sum < target: |
| 7 | left += 1 |
| 8 | else: |
| 9 | right -= 1 |
| 10 | return [] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Discarding an entire endpoint after a single comparison feels risky — how do you know you're not throwing away the answer? Sortedness is what makes it provably safe.
⚖️ The Analogy: A Seesaw You Can Only Push From the Ends
Picture the smallest and largest numbers sitting on opposite ends of a seesaw. If their combined sum is too big, the only way to bring it down is to swap out the larger end for something smaller — so you move the right pointer inward. If the sum is too small, the only way to raise it is to swap out the smaller end for something bigger — so you move the left pointer inward. Because the array is sorted, moving a pointer inward is the only direction that can fix an over/under-shoot; moving it the other way would only make the imbalance worse.
🔑 The Key Idea in the Code
Every element you discard when you move a pointer is provably eliminated: if numbers[left] + numbers[right] > target, then numbers[left] + numbers[anything smaller than right] is also too big, since the array is sorted — so skipping every intermediate right value is completely safe.
1-based indexing on the return value: LC 167 requires the 1-indexed positions
[left + 1, right + 1], not the raw 0-indexedleft/right; returning 0-indexed positions passes every trace by eye but fails the judge.Moving both pointers after a mismatch: only the pointer the comparison rules out may move; moving both skips pairs, so
numbers = [1, 2, 4, 6],target = 8never checks2 + 6.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array + find the pair that adds up to target, answered as 1-indexed positions, with only O(1) extra space: squeeze from both ends (Converging Pointers).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every pair that uses an index outside [left, right] cannot sum to target; one comparison of numbers[left] + numbers[right] with target rules out one more index.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Unsorted input: moving a pointer no longer raises or lowers the sum, so the squeeze can walk past the answer; the array must be sorted (LC 167 promises it).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Converging Pointers: left starts at index 0 and right at the last index. Because numbers is sorted, if the sum is smaller than target, numbers[left] is already paired with the largest value still available, so it can never reach target and I move left forward. If the sum is too big, numbers[right] is already paired with the smallest value still available, so I move right back. Each step rules out one element for good, which is why the pair can never be skipped. The trap is input that is not sorted: then moving a pointer no longer raises or lowers the sum, so the squeeze can walk past the answer. For unsorted input I would use a hash map, or sort value and index pairs to keep the original positions. Here the input is sorted and 1-indexed, so I return left + 1 and right + 1. It's
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the while loop: while left < right:. In each iteration, we evaluate current_sum = numbers[left] + numbers[right]. If the sum is too small, we increment left += 1; if too large, we decrement right -= 1. Because the distance (right - left) strictly decreases by 1 on every step, the loop executes at most N-1 times with O(1) arithmetic per step, yielding strictly O(N) time.
O(1) Auxiliary
Look at memory allocation: The search is iterative with O(1) call stack frames. We only store two scalar pointer variables (left, right) and one scalar sum accumulator. Auxiliary space is strictly O(1) in-place.
∑ (delta L + delta R) ≤ N ⟹ O(N)
Derivation Progression
(right - left) decreases by 1 each step
Sorted order guarantees that adjusting left rightward increases the sum and adjusting right leftward decreases the sum.
O(1) Arithmetic Per StepO(1) sum check
Testing current_sum == target takes constant time with zero inner loops.
N - 1 maximum steps ⟹ O(N)
The pointers converge from opposite ends, inspecting at most N elements before finding the pair.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative loop with zero recursion frames
O(1) Only scalar pointers (left, right) in CPU registers
O(1) Returns 2-element index list
Boundary Best / Worst Cases
if outer pair sums to target.
.
when pair is in the middle.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "array is already sorted in non-decreasing order", "find two numbers that add up to target", "O(1) extra space". Converging opposite-direction pointers exploiting monotonic ordering.
. Time budget strictly , space strictly .
Values stay within , so the sum cannot overflow here.