Hashing — Two Sum II (Input Array Is Sorted)
↗ LeetCode: Two Sum II - Input Array Is Sorted · Medium · pattern chapter →
Asked atMetaAmazonGoogle
Sorted array; return 1-indexed pair summing to target.
Example 1 — numbers=[2,7,11,15], target=9 → [1,2]Example 2 — numbers=[2,3,4], target=6 → [1,3]Example 3 — numbers=[-1,0], target=-1 → [1,2]
Constraints — 2 ≤ n ≤ 3·10⁴. Brute nested loop is O(n²) = 10⁸ ops at n=3·10⁴. Two-pointer inward sweep is O(n) = ~10⁶ pointer ops at scale.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Hash-map
Ignores sortedness. O(n) time O(n) space.
Approach 2 — Opposing two-pointer (canonical)
Insight. Sum monotone in pointer movement — deterministic.
java
int[] twoSum(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int s = nums[l] + nums[r];
if (s == target) return new int[]{l + 1, r + 1};
if (s < target) l++; else r--;
}
return new int[]{-1, -1};
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Hash map | O(n) | O(n) | works but wastes sort |
| Opposing 2p | O(n) | O(1) | canonical |
When to use which
- Sorted input → 2p every time.
- Not sorted → hash.
- k-Sum on sorted → recursion with 2p base.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems