A bridge of numbered stones crosses the chasm to the boss's gate. The numbers never go down from left to right: the bridge is sorted. The gate opens only for two stones whose numbers add up to exactly target.
Two knights stand on the bridge, one on the first stone and one on the last. They can only walk along it, one stone at a time, and you have no room to write anything down: no set, no map, no copy of the bridge.
Write find_stones(stones: list[int], target: int) -> list[int] that returns [i, j]: the positions of the two stones, counting from 1, with i < j and stones[i - 1] + stones[j - 1] == target.
- The bridge is built so that exactly one such pair of positions exists.
- Two stones can carry the same number, but one stone can't be used twice.
find_stones([2, 5, 9, 13, 17, 21, 26, 34, 37, 44], 50) # [4, 9] (13 + 37)
find_stones([3, 3, 8], 6) # [1, 2]
find_stones([-4, 1, 6, 10], 2) # [1, 3] (-4 + 6)
Constraints: 2 <= len(stones) <= 2 * 10^5; -10^9 <= stones[i] <= 10^9, in non-decreasing order; -2 * 10^9 <= target <= 2 * 10^9.
Checking every pair is O(n²), far too slow at this size. Aim for O(n) time and O(1) extra space.
Show hint
add the two knights' stones. If the sum is too small, can the left knight's stone ever be part of the answer?