LeetCode 167 — Two Sum II (Input Array Is Sorted) | Full Solution Explained

Difficulty	Pattern	Companies	Leetcode Link
Medium	Two Pointers	Amazon, Google, Microsoft, Adobe	leetcode.com/problems/two-sum-ii-input-array-is-sorted

📌  Before reading this post, I recommend reading the Two Pointers Pattern Guide on this blog. It will make this solution click much faster.

If you’ve solved the original Two Sum (LeetCode #1), you might think this is the same problem. It’s not — and that one small difference (the array is sorted) completely changes the best approach.

This problem is a textbook example of the Two Pointers pattern. Once you understand why the solution works — not just what the solution is — you’ll be able to apply the same logic to dozens of other problems.

Let’s go through everything from scratch.

The Problem

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

Return the indices of the two numbers (1-indexed) as an integer array of length 2.

Constraint	What it means for us
Array is sorted (non-decreasing)	We can use Two Pointers — smaller values on left, larger on right
Exactly one solution exists	We don’t need to handle ‘no answer’ case
1-indexed output	Return index+1 for both answers
Cannot use same element twice	Both pointers must point to different positions
Must use O(1) extra space	No hash map allowed — this forces the Two Pointers approach

Examples

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

Step 1 — The Brute Force Approach (and Why It’s Not Good Enough)

Before jumping to the optimal solution, let’s think about brute force. This is how most people approach the problem first — and it’s perfectly fine to start here.

The brute force idea: check every possible pair of numbers. For each element at index i, loop through every element at index j (where j > i) and check if they add up to the target.

Brute force

// Brute Force — O(n²) time
int n = nums.size();
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (nums[i] + nums[j] == target) {
            return {i + 1, j + 1};  // 1-indexed
        }
    }
}

Metric	Brute Force	Why it’s a problem
Time Complexity	O(n²)	Two nested loops — too slow for large inputs
Space Complexity	O(1)	No extra space — this part is fine
LeetCode Verdict	TLE	Will fail on large test cases (Time Limit Exceeded)

⚠️  The brute force works logically but gets TLE on LeetCode for large inputs. The interviewer will ask: ‘Can you do better?’ — and the answer is yes, using Two Pointers.

Step 2 — Build the Intuition (How to Think About It)

Here’s the key question: what does it mean that the array is sorted?

It means the smallest element is on the left and the largest is on the right. This gives us something very powerful — we can make smart decisions about which direction to move based on whether our current sum is too small or too big.

🤔  Imagine you start with one pointer at the leftmost element (smallest) and one pointer at the rightmost element (largest). Their sum is either equal to the target, less than the target, or greater than the target.

Current Sum vs Target	What it tells us	What we do
sum == target	Found it!	Return the indices
sum < target	We need a bigger sum	Move LEFT pointer right (increase the smaller number)
sum > target	We need a smaller sum	Move RIGHT pointer left (decrease the larger number)

💡  This works ONLY because the array is sorted. If we need a bigger sum, moving left pointer right always increases the sum. If we need a smaller sum, moving right pointer left always decreases it. This guarantee disappears in an unsorted array.

With this logic, each step either finds the answer or eliminates at least one element from consideration. We never need to backtrack. That’s why this runs in O(n).

Step 3 — Full Dry Run (Trace Every Step)

Let’s trace through Example 1 in detail.

Dry Run

Array:  [2,  7,  11,  15]
Index:   0   1    2    3   (0-based internally, 1-based for output)
Target: 9

Step	left	right	nums[left]	nums[right]	Sum	Decision
1	0	3	2	15	17	17 > 9  →  move right left
2	0	2	2	11	13	13 > 9  →  move right left
3	0	1	2	7	9	9 == 9  →  FOUND! return [1, 2]

✅  Answer found in just 3 steps on an array of size 4. Brute force would have taken up to 6 comparisons. On large arrays, the difference is enormous.

Now let’s trace Example 2 as well to make sure we fully understand.

Dry Run

Array:  [2,  3,  4]
Index:   0   1   2
Target: 6

Step	left	right	numbers[left]	numbers[right]	Sum	Decision
1	0	2	2	4	6	6 == 6  →  FOUND! return [1, 3]

And one more — a case where the pointers have to cross the array before finding the answer.

Dry Run

Array:  [1,  2,  3,  4,  6]
Index:   0   1   2   3   4
Target: 6

Step	left	right	numbers[left]	numbers[right]	Sum	Decision
1	0	4	1	6	7	7 > 6   →  move right left
2	0	3	1	4	5	5 < 6   →  move left right
3	1	3	2	4	6	6 == 6  →  FOUND! return [2, 4]

Step 4 — The Optimal Solution (Two Pointers)

Now that we fully understand why the approach works, let’s write the clean solution in all three languages.

C++ Solution

#include <vector>
using namespace std;
 
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;                       // start from leftmost (smallest)
        int right = numbers.size() - 1;    // start from rightmost (largest)
 
        while (left < right) {
            int sum = numbers[left] + numbers[right];
 
            if (sum == target) {
                // found! return 1-indexed positions
                return {left + 1, right + 1};
 
            } else if (sum < target) {
                // sum too small — need bigger number
                // move left pointer right to increase sum
                left++;
 
            } else {
                // sum too big — need smaller number
                // move right pointer left to decrease sum
                right--;
            }
        }
 
        // problem guarantees exactly one solution
        // we will never reach here
        return {};
    }
};

Python Solution

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left = 0                    # start from leftmost (smallest)
        right = len(numbers) - 1   # start from rightmost (largest)
 
        while left < right:
            current_sum = numbers[left] + numbers[right]
 
            if current_sum == target:
                # found! return 1-indexed positions
                return [left + 1, right + 1]
 
            elif current_sum < target:
                # sum too small — need bigger number
                # move left pointer right to increase sum
                left += 1
 
            else:
                # sum too big — need smaller number
                # move right pointer left to decrease sum
                right -= 1
 
        # problem guarantees exactly one solution
        # we will never reach here
        return []

JavaScript Solution

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;                       // start from leftmost (smallest)
    let right = numbers.length - 1;    // start from rightmost (largest)
 
    while (left < right) {
        const sum = numbers[left] + numbers[right];
 
        if (sum === target) {
            // found! return 1-indexed positions
            return [left + 1, right + 1];
 
        } else if (sum < target) {
            // sum too small — need bigger number
            // move left pointer right to increase sum
            left++;
 
        } else {
            // sum too big — need smaller number
            // move right pointer left to decrease sum
            right--;
        }
    }
 
    // problem guarantees exactly one solution
    return [];
};

Step 5 — Complexity Analysis

Metric	Brute Force	Two Pointers	Why
Time Complexity	O(n²)	O(n)	Each pointer moves at most n steps total
Space Complexity	O(1)	O(1)	Only two integer variables — no extra array or map

🚀  The Two Pointers solution visits each element at most once. Left pointer only moves right. Right pointer only moves left. Total moves = at most n. Hence O(n).

Let’s verify why it’s O(n) more precisely:

• left starts at 0 and can only increase — maximum n moves
• right starts at n-1 and can only decrease — maximum n moves
• Together, they make at most n total moves before left >= right
• Each move does O(1) work (just an addition and comparison)
• Total: O(n) time, O(1) space

Step 6 — Why Not Use a Hash Map Here?

Good question. In the original Two Sum (LeetCode #1), we used a hash map to get O(n) time. So why not do the same here?

Approach	Time	Space	Works here?
Hash Map (like Two Sum I)	O(n)	O(n)	Yes, but violates the O(1) space constraint
Two Pointers	O(n)	O(1)	Yes — and satisfies all constraints
Binary Search (per element)	O(n log n)	O(1)	Works, but slower than Two Pointers

💡  The problem explicitly says ‘use only constant extra space’. This is the interviewer’s hint that a hash map is not the expected solution — Two Pointers is.

Beyond the constraint, Two Pointers is actually the more elegant solution here. It takes advantage of the sorted property in a way that makes the logic intuitive and clean.

Step 7 — Edge Cases to Think About

Even though the problem guarantees exactly one solution, it’s good practice in interviews to think through edge cases. Shows the interviewer you think carefully.

Edge Case	Does our solution handle it?
Answer is first and last element (index 0 and n-1)	Yes — initial left=0, right=n-1 catches this in first step
Two adjacent elements are the answer	Yes — eventually left and right will be adjacent
Negative numbers in the array	Yes — Two Pointers works with negatives, we only care about sum
Array of size 2	Yes — left=0, right=1, one comparison, done
All elements are the same	Yes — handled correctly since we check sum == target

✅  Our solution handles all these cases correctly without any special case code. That’s the beauty of a clean Two Pointers implementation.

Step 8 — How to Explain This in an Interview

Knowing the solution is one thing. Communicating it clearly under pressure is another. Here’s the exact approach to use in a technical interview:

1. Clarify the problem: ‘The array is sorted and 1-indexed output — confirmed?’
2. State brute force first: ‘A brute force approach would check every pair — O(n²) time. But since the array is sorted, we can do better.’
3. Explain the intuition: ‘Since it’s sorted, smallest values are on the left and largest on the right. I’ll start one pointer at each end and move them based on whether the sum is too big or too small.’
4. Dry run on the example: Trace through the given example on paper/whiteboard before coding.
5. Write the code: Clean, commented, no syntax errors.
6. State complexity: ‘Time O(n), Space O(1) — each pointer moves at most n steps.’
7. Check edge cases: Walk through at least one edge case verbally.

⚠️  Don’t jump straight to code. Interviewers at product companies (Google, Amazon, Microsoft) care as much about your thought process as your final solution. Explain before you code.

Two Sum I vs Two Sum II — Quick Comparison

Since many people confuse these two, here’s a side-by-side comparison:

Feature	Two Sum I (LeetCode #1)	Two Sum II (LeetCode #167)
Array sorted?	No — unsorted	Yes — sorted (non-decreasing)
Best approach	Hash Map	Two Pointers
Time Complexity	O(n)	O(n)
Space Complexity	O(n) — for the map	O(1) — no extra space
Output format	0-indexed	1-indexed
Multiple solutions?	Return any one	Exactly one solution guaranteed

💡  Remember: when an array is sorted and the problem asks for a pair satisfying some condition — always think Two Pointers first. It gives O(n) time AND O(1) space.

Final Solution at a Glance

C++

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if      (sum == target) return {left + 1, right + 1};
        else if (sum <  target) left++;
        else                    right--;
    }
    return {};
}

Time Complexity	Space Complexity	LeetCode Result	Difficulty
O(n)	O(1)	Accepted ✓	Medium

Wrapping Up

LeetCode 167 is a perfect problem to solidify your understanding of the Two Pointers pattern. It’s not just about memorising this one solution — it’s about internalising the logic:

• Sorted array? Think Two Pointers.
• Sum too small? Move left pointer right.
• Sum too big? Move right pointer left.
• This approach — one pointer from each end, moving based on conditions — works for Container With Most Water, 3Sum, Trapping Rain Water, and many more.

Once this pattern is in your muscle memory, you’ll solve medium-level array problems significantly faster in interviews.

📬  This problem is part of the Two Pointers series on Daily Dev Notes. Next up: LeetCode 11 — Container With Most Water. Subscribe to the newsletter so you don’t miss it.

Have a question about a specific step? Drop it in the comments — I reply to every one