Pair Sum in Sorted Array

Problem

Given arr sorted in ascending order and an integer target, find two distinct indices i < j with arr[i] + arr[j] == target, and return them as [i, j].

Use the two-pointer technique in O(n) time: move the left pointer up when the sum is too small and the right pointer down when it is too large. Return an empty list if no such pair exists.

Hint

Start with pointers at both ends and move them inward based on the current sum.

Test cases

case 1

in: [[1,2,3,4,6],6]

expected: [1,3]

case 2

in: [[2,3,4],6]

expected: [0,2]

case 3

in: [[1,1],2]

expected: [0,1]

case 4

in: [[-3,-1,2,4],1]

expected: [0,3]

case 5

in: [[1,2],10]

expected: []

Starter codePython

def pair_sum_sorted(arr, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor