0100MediumArrayTwo PointersBinary Search

Rail Grade Offset Pair

Tracked in this browser only

Trains the technique from

LeetCode 167Two Sum II - Input Array Is Sorted

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_offset_pair(offsets: list[int], target: int) -> list[int]:

Java

public int[] findOffsetPair(int[] offsets, int target)

The intended approach

Time O(n)Space O(1)

Because the offsets are sorted, park one cursor at the low end and one at the high end and read their sum. A sum below the target can only be raised by giving up the smallest offset, and a sum above it can only be lowered by giving up the largest, so each step discards exactly one marker that cannot belong to the answer. The cursors meet after one sweep and need no extra storage.

Pythonentry point: find_offset_pair

def find_offset_pair(offsets, target):
    low, high = 0, len(offsets) - 1
    while low < high:
        total = offsets[low] + offsets[high]
        if total == target:
            return [low + 1, high + 1]
        if total < target:
            low += 1
        else:
            high -= 1
    return []

The obvious version

Try every marker pair in index order and return the first that adds up to the target. O(n^2) time, ignores the constant-space rule.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_offset_pair(offsets, target):
    n = len(offsets)
    for i in range(n):
        for j in range(i + 1, n):
            if offsets[i] + offsets[j] == target:
                return [i + 1, j + 1]
    return []

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in