Pair with Target Sum

ArrayHash TableTwo Pointers

Given an array of sorted integers and a target sum, find a pair of numbers in the array that adds up to the given target. Return the indices of the two numbers in a tuple or array, where the index of the first number is strictly less than the index of the second number.

Example 1

Input

[
  1,
  2,
  3,
  4
]

Output

[0, 2]

Explanation. The numbers at index 0 and 2 (1 and 3 respectively) add up to the target sum of 4.

Example 2

Input

[
  1,
  2,
  3,
  4,
  7
]

Output

[2, 4]

Explanation. The numbers at index 2 and 4 (3 and 7 respectively) add up to the target sum of 10.

Example 3

Input

[
  2,
  3,
  4,
  4,
  6,
  7
]

Output

[0, 5]

Explanation. The numbers at index 0 and 5 (2 and 7 respectively) add up to the target sum of 9.

Example 4

Input

[
  2,
  3,
  4,
  4,
  6,
  7
]

Output

[]

Explanation. There is no pair of numbers in this array that adds up to the target sum of 20.

Follow-up: How would you handle the problem if the given array is not sorted? Discuss and possibly modify your solution to accommodate this scenario.

Constraints:

- The input array will contain at least two integers and will be sorted in non-decreasing order. - If no such pair exists, return an empty array.

Views: 3