Find a pair that adds up to a target — interview question

You are given a list of integers and a target value. Find two different positions i < j whose values add up to the target.

If several pairs work, report the one whose second position j is as small as possible; if that still leaves a choice, use the smallest i. If no pair exists, print -1 -1.

Constraints

2 ≤ n ≤ 100000
−10^9 ≤ a[i], target ≤ 10^9

Input and output

Input: Line 1: n Line 2: n integers a[0..n−1] Line 3: target
Output: Two integers i and j (0-based), or -1 -1.

Examples

Input 1

5
4 9 2 7 5
11

Output

1 2

9 (index 1) + 2 (index 2) = 11; j = 2 is the earliest possible second position.

Input 2

4
3 3 4 1
6

Output

0 1

The two 3s.

Show hints

For each position j, which value would complete the pair?
Remember the first position where each value appeared.

Show the explanation

Scan left to right and keep a map from value → first index where it appeared. At position j, the partner we need is target − a[j]. If it is already in the map, that stored index is the smallest valid i for the smallest valid j, so we can stop. Otherwise record a[j] (only if it is not already stored, to keep the first index).

Time: O(n) expected. Space: O(n).

A nested loop also works but is O(n²) and too slow for n = 100000. Watch for overflow: the sum of two values can exceed a 32-bit int, so use 64-bit arithmetic.

Original UniCircle question. Last reviewed 21 Oct 2026.