Two sum in a sorted list

Easy

2000 ms limit256 MB memoryTwo pointers Binary search Arrays

Stuck?

Show a hint

Start with one index at each end. If the sum is too big, move the right one in. If too small, move the left one out.

The ideas behind this problem

Two pointers: replacing a nested loop with a single pass Binary search, and getting the boundary right

Next in this lesson

The best k days in a row

Given a list of numbers already in increasing order, find the two that add up to a target. Return their positions, smaller first.

Worked example#

For [2, 7, 11, 15] with target 9, put one finger at each end:

left	right	2 + 15 = 17	too big, so move the right finger in
2	15	17	too big, move right in
2	11	13	too big, move right in
2	7	9	found it, positions 0 and 1

Why moving inward is safe: the list is sorted, so moving the right finger left always makes the sum smaller, and moving the left finger right always makes it bigger. Each step rules out a whole set of pairs at once rather than testing them one by one.

This is the payoff for sorted input. Without the ordering you would need a hash map; with it, two fingers walking toward each other are enough.

Constraints#

2 <= n <= 100000
The list is in increasing order
Exactly one pair adds up to the target

Input

nums is a count then that many integers, in increasing order. target is one integer.

Output

The two positions, smaller first, separated by a space.

Examples

Input

4
2 7 11 15
9

Output

0 1

2 + 7 = 9. The fingers meet after moving the right one in twice.

Input

4
1 2 3 4
7

Output

2 3

3 + 4 = 7, which is the pair at the right end.

Input

3
-3 0 3
0

Output

0 2

Negative numbers work the same way: -3 + 3 = 0.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.