Plaintext
================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================
# 180-Day DSA Roadmap | Day 1: Two Sum II (Input Array Is Sorted)
* **Topic:** Arrays & Strings
* **Pattern:** Two Pointers (Opposite Ends / Inward Scan)
* **Difficulty:** Medium
* **LeetCode Problem:** LeetCode #167 - Two Sum II (Input Array Is Sorted)
* **Target Companies:** Amazon, Google, Microsoft, Meta, Bloomberg
---
## 1. Problem Statement
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` number.
Let these two numbers be `numbers[index1]` and `numbers[index2]` where `1 <= index1 < index2 <= numbers.length`.
Return the indices of the two numbers, `index1` and `index2`, added by one as an integer array `[index1, index2]` of length 2.
### Constraints
* 2 <= numbers.length <= 3 * 10^4
* -1000 <= numbers[i] <= 1000
* `numbers` is sorted in non-decreasing order.
* -1000 <= target <= 1000
* Exactly one valid solution exists.
* You cannot use the same element twice.
* Must use strictly O(1) auxiliary space.
### Example Walkthrough
```text
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
2. Pattern Recognition: Why Two Pointers?
In technical interviews, use this 30-second checklist to spot when the Opposite-Direction Two-Pointer technique applies:
- The Array is Already Sorted: When an array is ordered monotonically, moving left or right produces predictable, monotonic changes in values.
- Finding a Complementary Pair: The problem asks for two elements that satisfy: A + B = Target.
- Strict O(1) Auxiliary Space: While classic Two Sum uses a Hash Map in O(N) space, this sorted variation specifically tests whether you can eliminate the hash map entirely and run in constant memory.
3. Algorithmic Approaches
Approach 1: Brute Force (Suboptimal)
- Check every possible pair (i, j) using two nested loops.
- Time Complexity: O(N^2)
- Space Complexity: O(1)
- Verdict: Fails with Time Limit Exceeded (TLE) on large inputs.
Approach 2: Binary Search (Suboptimal)
- For each element
numbers[i], perform a binary search on the remaining array fortarget - numbers[i]. - Time Complexity: O(N log N)
- Space Complexity: O(1)
- Verdict: Works, but fails to use the linear two-pointer invariant.
Approach 3: Optimal Two Pointers (The MNC Standard)
- Place a pointer
leftat the start (0) andrightat the end (numbers.length - 1). - Calculate
current_sum = numbers[left] + numbers[right]:- If current_sum == target: Pair found! Return
[left + 1, right + 1]. - If current_sum < target: The sum is too small. Because the array is sorted, incrementing
left++increases the sum. - If current_sum > target: The sum is too large. Decrementing
right--decreases the sum.
- If current_sum == target: Pair found! Return
Plaintext
Visual Execution Trace (Target = 9):
Step 1:
[ 2 , 7 , 11 , 15 ]
â–² â–²
left right Sum = 2 + 15 = 17 (> 9) ──► right--
Step 2:
[ 2 , 7 , 11 , 15 ]
â–² â–²
left right Sum = 2 + 11 = 13 (> 9) ──► right--
Step 3:
[ 2 , 7 , 11 , 15 ]
â–² â–²
left right Sum = 2 + 7 = 9 (== target) ──► MATCH FOUND!
4. Production-Ready Code Implementations
Java Solution
Java
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int currentSum = numbers[left] + numbers[right];
if (currentSum == target) {
return new int[] { left + 1, right + 1 };
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
return new int[] {};
}
}
Python 3 Solution
Python
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
left = 0
right = len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right -= 1
return []
C++ Solution
C++
#include <vector>
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size() - 1;
while (left < right) {
int currentSum = numbers[left] + numbers[right];
if (currentSum == target) {
return {left + 1, right + 1};
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
return {};
}
};
5. Complexity Analysis
- Time Complexity: O(N) — At each step, either
leftincreases orrightdecreases. Pointers meet after at most N iterations. - Space Complexity: O(1) — No hash tables, recursion, or extra allocations used.
6. Key Takeaways & Interview Traps
- 1-Based Output Trap: LeetCode #167 requires 1-based indexing (
left + 1,right + 1), unlike standard 0-indexed arrays. - Monotonicity Guarantee: Because the array is sorted, every pointer movement safely rules out all combinations in that direction without checking each one individually.
Master the Two-Pointer Technique: LeetCode 167 (Two Sum II) Explained | Day 1 of 180
META DESCRIPTION:
Master LeetCode 167 (Two Sum II) using the two-pointer technique. Learn pattern recognition, O(1) space optimization, and code in Java, Python, and C++.
Two Sum II LeetCode 167, Two Pointer Technique DSA, LeetCode 167 Solution Java Python Cpp, DSA Interview Questions Sheet
leetcode 167, two sum ii, two pointer technique, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, two pointers pattern, leetcode easy medium, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, leetcode 167 java, leetcode 167 python, leetcode 167 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, binary search vs two pointers, sorted array two sum, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, off campus drive 2026, software development engineer, sde 1 preparation, array algorithms, inplace algorithms, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap, algorithm patterns, technical interview tips, leetcode daily streak, dsa sheet solutions