Two Pointers (Pair Sum) - Classic Problems | Repovive

CLS27. Two Pointers (Pair Sum)

1s256 MB

Given a sorted array of $n$ integers in non-decreasing order and a target sum $S$ , find two elements at different positions that add up to $S$ .

Output the two values in increasing order. If no such pair exists, output $-1$ .

If multiple valid pairs exist, output the one with the smallest first value.

\begin{array}{l} n \quad S \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

\begin{cases} a_i \quad a_j & \text{if pair exists} \\ -1 & \text{otherwise} \end{cases}

Input

5 9
1 2 4 5 7

Explanation

For this input, the required output is 2 7.

Output

2 7

Input

4 10
1 2 3 4

Explanation

For this input, the required output is -1.

Output

-1

Input

6 0
-5 -3 -1 1 3 5

Explanation

For this input, the required output is -5 5.

Output

-5 5

1s256 MB

Given a sorted array of $n$ integers in non-decreasing order and a target sum $S$ , find two elements at different positions that add up to $S$ .

Output the two values in increasing order. If no such pair exists, output $-1$ .

If multiple valid pairs exist, output the one with the smallest first value.

\begin{array}{l} n \quad S \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

\begin{cases} a_i \quad a_j & \text{if pair exists} \\ -1 & \text{otherwise} \end{cases}

Input

5 9
1 2 4 5 7

Explanation

For this input, the required output is 2 7.

Output

2 7

Input

4 10
1 2 3 4

Explanation

For this input, the required output is -1.

Output

-1

Input

6 0
-5 -3 -1 1 3 5

Explanation

For this input, the required output is -5 5.

Output

-5 5