Published on

# Easy: Pair with Target Sum

Authors

## Problem Statement

Given an array of sorted numbers 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.

Example 1:

_3
Input: [1, 2, 3, 4, 6], target=6
_3
Output: [1, 3]
_3
Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6

Example 2:

_3
Input: [2, 5, 9, 11], target=11
_3
Output: [0, 2]
_3
Explanation: The numbers at index 0 and 2 add up to 11: 2+9=11

## Try it yourself

_26
package main
_26
_26
import (
_26
"reflect"
_26
"testing"
_26
)
_26
_26
func PairTargetSum(input []int, x int) []int {
_26
_26
return []int{0, 0}
_26
}
_26
_26
func TestLastIndex(t *testing.T) {
_26
tests := []struct {
_26
list []int
_26
target int
_26
want []int
_26
}{
_26
{list: []int{1, 2, 4, 4, 6}, target: 6, want: []int{1, 3}},
_26
}
_26
for _, tt := range tests {
_26
if got := PairTargetSum(tt.list, tt.target); !reflect.DeepEqual(got, tt.want) {
_26
t.Errorf("LastIndex(%v, %v) = %v, want %v", tt.list, tt.target, got, tt.want)
_26
}
_26
}
_26
}

Or try it online using https://go.dev/play/p/vcZ6N-TTvA0

## Solution

One way to solve this problem for a sorted array is to use a brute-force approach, which involves iterating through the array, checking one number at a time and searching for the second number using Binary Search. However, this approach has a time complexity of O(N*logN).

Alternatively, we can use the Two Pointers approach to solve this problem more efficiently. This involves using two pointers - one pointing to the beginning of the array and the other pointing to the end. At each step, we check if the sum of the numbers pointed to by the two pointers equals the target sum. If it does, we have found a pair; otherwise, we adjust the pointers based on whether the sum is greater or smaller than the target sum. If the sum is greater, we decrement the end-pointer to try more pairs with smaller sums. If the sum is smaller, we increment the start-pointer to try more pairs with larger sums. The Two Pointers approach has a better time complexity compared to the brute-force approach.

_39
package main
_39
_39
import (
_39
"reflect"
_39
"testing"
_39
)
_39
_39
func PairTargetSum(input []int, targetSum int) []int {
_39
left, right := 0, len(input)-1
_39
for left < right {
_39
sum := input[left] + input[right]
_39
if sum == targetSum {
_39
return []int{left, right}
_39
}
_39
_39
if targetSum > sum {
_39
left++ // need pair with bigger sum
_39
} else {
_39
right-- // need pair with smaller sum
_39
}
_39
}
_39
return []int{-1, -1}
_39
}
_39
_39
func TestLastIndex(t *testing.T) {
_39
tests := []struct {
_39
list []int
_39
target int
_39
want []int
_39
}{
_39
{list: []int{1, 2, 4, 4, 6}, target: 6, want: []int{1, 3}},
_39
{list: []int{2, 5, 9, 11}, target: 11, want: []int{0, 2}},
_39
}
_39
for _, tt := range tests {
_39
if got := PairTargetSum(tt.list, tt.target); !reflect.DeepEqual(got, tt.want) {
_39
t.Errorf("LastIndex(%v, %v) = %v, want %v", tt.list, tt.target, got, tt.want)
_39
}
_39
}
_39
}

Try it online https://go.dev/play/p/N_85BJfEsOm

### Time complexity

The above algorithm has a time complexity of $O(N)$, where N is the total number of elements in the given array. This means that the time taken to execute the algorithm increases linearly with the number of elements in the array.

### Space complexity

The algorithm has a space complexity of $O(1)$, which means that it runs in constant space. This means that the amount of memory used by the algorithm remains constant, regardless of the size of the input array.