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:

_3Input: [1, 2, 3, 4, 6], target=6_3Output: [1, 3]_3Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6

Example 2:

_3Input: [2, 5, 9, 11], target=11_3Output: [0, 2]_3Explanation: The numbers at index 0 and 2 add up to 11: 2+9=11

## Try it yourself

_26package main_26_26import (_26 "reflect"_26 "testing"_26)_26_26func PairTargetSum(input []int, x int) []int {_26 // add your code here_26 return []int{0, 0}_26}_26_26func 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.

_39package main_39_39import (_39 "reflect"_39 "testing"_39)_39_39func 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_39func 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.