two-sum-ii-sorted

Difficulty: Easy  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/two-sum-ii-sorted/start

The story

Schwab's overnight reconciliation pipeline produces a sorted list of clearing-fee adjustments for the next business day. Each adjustment carries a signed value. The treasury team needs to know, on demand, whether any two adjustments together hit a target net amount (positive or negative), so they can pre-flag them for the morning ops desk. They will ask the question hundreds of times against the same sorted list with different targets, and the list can be tens of thousands of rows. They want a single-pass linear check, no hash maps, no extra memory.

That is two-sum-ii-sorted. The "sorted" is the entire reason this problem exists as its own beast. The unsorted two-sum wants a hash map; this one rejects that as wasteful because the data already has structure you should exploit.

What's actually being asked

Given a sorted (non-decreasing) integer array nums and an integer target, return the 1-based indices of two numbers that add up exactly to target. The problem guarantees at most one valid pair. If no pair exists, print -1. Indices must be in ascending order.

The naive approach

Two nested loops, exactly like two-sum. For n = 10^4 that is 50 million comparisons. Python will not finish that inside the 2-second limit. You can also reach for a hash map: O(n) time, O(n) space, ignores the sortedness, and the interviewer judges you for it. The point of this problem is to learn the cheap solution that the sortedness unlocks.

The key insight

When the array is sorted, the pair sum at the two ends is the largest pair when you take the leftmost and rightmost values. If you compare nums[l] + nums[r] to target:

• If the sum is exactly target, you are done.
• If the sum is too small, the only way to grow it is to increase the smaller side. Increment l.
• If the sum is too big, the only way to shrink it is to decrease the larger side. Decrement r.

Each step eliminates one element from contention forever. That is the monotone invariant. The loop runs at most n times.

The piece that trips people up: when you advance l because the sum is too small, you are committing to never re-examine the old l. Why is that safe? Because every value to the left of the current r is at most nums[r] (the array is sorted), so the best pair involving the old l is nums[l] + nums[r], which is already too small. No future pair involving the old l can fix that. Symmetric argument for the other side.

Step-by-step approach

1. Initialise l = 0, r = n - 1.
2. While l < r:
   • Compute s = nums[l] + nums[r].
   • If s == target, print l + 1 and r + 1 separated by a space, return.
   • If s < target, increment l.
   • Else, decrement r.
3. If the loop exits without a hit, print -1.

Worked example

nums = [-3, -1, 2, 4]
target = -4

Output: 1 2.

Try nums = [1, 2, 3], target = 10. The pointers walk to each other without ever hitting 10. Output: -1.

Complexity

• Time: O(n). Each pointer crosses the array at most once.
• Space: O(1).

Compare to brute force (O(n²) time) and hash map (O(n) time, O(n) space). Two pointers beats both on this input shape.

Common pitfalls

• Off-by-one on the indices: the problem asks for 1-based, not 0-based. Print l + 1 and r + 1.
• Using <= instead of < in the loop condition: when l == r you would consider pairing a value with itself.
• Forgetting the "no pair" case and printing nothing instead of -1.
• Overflow in lower-level languages: nums[l] + nums[r] can overflow 32-bit signed when both are near the limit. Python integers are arbitrary precision so the limit constraints in this problem are a non-issue, but in C++ you would reach for long long.
• Sorting an unsorted input as a "general solution": that loses the original indices, which is exactly why this variant exists as a separate problem from two-sum.

Where this shows up in the enterprise

• Schwab / Fidelity reconciliation: matching pairs of adjustments that net to a target in a pre-sorted ledger.
• AWS Cost Explorer: finding two consolidated service charges that sum to a custom budget threshold, on already-sorted monthly aggregates.
• Stripe Radar: pair-of-transactions queries against time-sorted ledgers for the same merchant where the analyst is hunting for a structuring pattern.
• Bloomberg trade reconciliation: two opposing tickets on a sorted intraday tape that net to a target P&L.
• LinkedIn skill graph: pre-sorted skill scores per profile, find two skills whose summed weight matches a recruiter's gate.
• Spotify "Wrapped" generation: minutes listened per track, sorted, pair-of-tracks whose total equals an hour milestone.
• Wayfair pricing: sorted product price list, pair that hits a free-shipping target.

The pattern is "sorted data, pair-sum question". Any system that maintains its data sorted (and most ledgers and time-series do) prefers this O(n) two-pointer solution to a hash map.

Variants you'll see elsewhere

• two-sum: unsorted input, hash map is the right tool.
• three-sum: sort, fix one element, run two pointers on the rest.
• three-sum-closest: find a triplet whose sum is closest to a target, same skeleton with a running best.
• four-sum / k-sum: same insight, k-2 nested loops, two pointers at the end.
• container-with-most-water: also converging pointers on a sorted-by-index array, but the move rule is "move the shorter side".

The whole k-sum family is this insight applied repeatedly.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases hammer the no-pair branch, the duplicate values branch ([5, 5, 5, 5] target 10), and large negatives at the boundaries.
2. Hints are graduated. Level 1 asks "what does sortedness let you do?". Level 4 hands you the full algorithm at a penalty. The integrity score tracks how independently you reasoned.
3. The AI training assistant offers Explain, Review, Find Bugs, Add Comments, Optimise in exam mode, each at an integrity cost. In practice mode AI chat is free and free-form.
4. The dispute flow is the safety net: if the verdict is wrong, one click sends the code to a human reviewer who can override.

Read this concept first, attempt the problem in practice mode, take a hint only when you actually need one, then redo it in exam mode with no help. When you can write the two-pointer version inside three minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

1. Recognise that the problem is "pair-sum on sorted data" the moment the spec mentions a sorted input. The five-second recognition is the entire skill.
2. Tell the agent precisely: "two pointers, converging, move the side that explains the gap". Not "find two values that sum to X", that wording invites a hash map.
3. Read the agent's code and check three things: the loop guard is l < r (not <=), the output is 1-based, the no-pair branch returns -1.
4. Stress-test what the agent silently gets wrong: pairs that include duplicates, the empty-result case, and the boundary target == 2 * nums[0] where the answer might be the very first two indices.

Candidates who can name "this is sorted two-sum, use converging pointers" within five seconds are the ones who direct AI agents productively. Candidates who reach for a hash map every time end up with O(n) extra memory in a system that explicitly forbade it. parikshan is built to train the first kind.