Sorted Pair Hunt

medium

A thrift store keeps its price tags in a sorted tray. A customer has a voucher worth exactly target and wants two items that use it to the cent.

Given prices sorted in non-decreasing order, return the indices [i, j] (0-based, i < j) of two items whose prices sum to target. Exactly one such pair exists.

The tray is sorted — your solution should exploit that with O(1) extra space. (A hash map works on unsorted data but pays O(n) memory; here you can do better.)

Example 1

in prices = [1, 3, 4, 6, 9], target = 10

out [1, 4]

prices[1] + prices[4] = 3 + 9 = 10.

Example 2

in prices = [2, 5, 5], target = 10

out [1, 2]

Constraints

· 2 <= len(prices) <= 10^5
· -10^9 <= prices[i], target <= 10^9
· prices is sorted non-decreasing
· exactly one valid pair exists