Sorted Ledger Pair
EasyTwo PointersFree
Problem
An accountant keeps a list of transaction amounts nums sorted in non-decreasing order. Exactly one pair of different positions i < j has amounts that add up to target.
Return [i, j]. Your solution must use only O(1) extra memory.
Example 1
- Input:
- nums = [1, 3, 4, 6, 11], target = 10
- Output:
- [2, 3]
nums[2] + nums[3] = 4 + 6 = 10.
Example 2
- Input:
- nums = [-5, -2, 0, 7], target = 5
- Output:
- [1, 3]
-2 + 7 = 5.
Example 3
- Input:
- nums = [2, 2], target = 4
- Output:
- [0, 1]
Constraints
- 2 ≤ nums.length ≤ 3·10^4
- -10^9 ≤ nums[i], target ≤ 10^9
- nums is sorted in non-decreasing order
- Exactly one valid pair exists.
Hint
Show the first hint
The array is sorted. What does comparing the current sum to the target tell you about which end to move?
Walkthrough
How to approach it
01Clarify before coding
- Are the indices 0-based? Yes, return [i, j] with i < j.
- Can there be duplicates? Yes, and two equal values at different positions may form the pair.
- Is a hash map allowed? It works, but the requirement is O(1) extra memory, so use the sorted order instead.
02Brute force
Try every pair (i, j) and return the one whose values sum to target.
Cost: O(n²) time, O(1) space: about 4.5·10^8 checks for n = 3·10^4, far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.