Pair with Target Sum

Easy·Tagsarraytwo-pointerssorting

Problem Statement

Given an array of numbers sorted in ascending order and a target sum, find a pair in the array whose sum is equal to the given target. Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target. If no such pair exists, return `[-1, -1]`. Note: Return the indices sorted in ascending order (i.e., `[smaller_index, larger_index]`).

Examples

Example 1

Input

arr: [1, 2, 3, 4, 6], target: 6

Output

"[1, 3]"

Why

Index 1 holds 2 and index 3 holds 4, and 2 + 4 equals the target 6, so we return the indices in ascending order as [1, 3].

Example 2

Input

arr: [2, 5, 9, 11], target: 11

Output

"[0, 2]"

Why

The values 2 and 9 sit at index 0 and index 2, and together they make the target 11, so the answer is [0, 2].

Example 3

Input

arr: [1, 2, 3], target: 7

Output

"[-1, -1]"

Why

No two values in the array add up to 7, so there is no valid pair and the result is [-1, -1].

Constraints

•2 <= arr.length <= 10000
•-10^9 <= arr[i] <= 10^9
•-10^9 <= target <= 10^9

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

The array is sorted in ascending order. That ordering is the key: it lets you decide which way to move at each step instead of testing every possible pair.

Hint 2

Put one pointer at the start (the smallest value) and one at the end (the largest value), then look at the sum of the two.

Hint 3

If the sum is smaller than the target, move the left pointer right to make it larger; if it is larger than the target, move the right pointer left to make it smaller. When the sum equals the target, you have found the pair.