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]
READ FULL ARTICLE: https://dailydevnotes.in/leetcode-167-two-sum-ii-two-pointers/
Top comments (0)