Show problems as
Classic problem #167MediumArrayTwo PointersBinary Search

Two Sum II - Input Array Is Sorted

Real-world version: Rail Grade Offset Pair
Tracked in this browser only
Read Two Sum II - Input Array Is Sorted on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey crew walks a rail line and records the grade offset at each marker, in centimetres above or below the design profile. The offsets arrive already sorted from lowest to highest, so equal offsets sit next to each other.

Given the array offsets and an integer target, find the two markers whose offsets add up to target. Report them as [first, second] using 1-based marker numbers with first < second. A marker may not be paired with itself, but two markers holding the same offset are a legal pair.

Only one pair ever adds up to target, so the answer is unique.

Your routine may allocate only a fixed number of extra variables: no auxiliary array, table or set whose size grows with the input.

Examples

Example 1

Input
offsets = [-8, -3, 1, 4, 9], target = 6
Output
[2, 5]

Marker 2 sits 3 cm low and marker 5 sits 9 cm high, so the pair adds up to 6.

Example 2

Input
offsets = [-6, -6, 2, 7], target = -12
Output
[1, 2]

The two deepest markers hold equal offsets and are separate markers, so pairing them is allowed.

Example 3

Input
offsets = [5, 12], target = 17
Output
[1, 2]

With two markers on the line there is only one pair to consider.

Constraints

  • 2 <= offsets.length <= 3 * 10^4
  • -1000 <= offsets[i] <= 1000
  • offsets is sorted in non-decreasing order
  • -1000 <= target <= 1000
  • Exactly one pair of markers adds up to target
  • Use only constant extra space

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_offset_pair(offsets: list[int], target: int) -> list[int]:
Java
public int[] findOffsetPair(int[] offsets, int target)

More on the same topics