# Easy: Pair with Target Sum

2 min read Tweet this post
Section titled Problem%20Statement

## 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:

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


Example 2:

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

Section titled Try%20it%20yourself

## Try it yourself

package main

import (
"reflect"
"testing"
)

func PairTargetSum(input []int, x int) []int {
return []int{0, 0}
}

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


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

Section titled Solution

## 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.

package main

import (
"reflect"
"testing"
)

func PairTargetSum(input []int, targetSum int) []int {
left, right := 0, len(input)-1
for left < right {
sum := input[left] + input[right]
if sum == targetSum {
return []int{left, right}
}

if targetSum > sum {
left++ // need pair with bigger sum
} else {
right-- // need pair with smaller sum
}
}
return []int{-1, -1}
}

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


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

Section titled Time%20complexity

### 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.

Section titled Space%20complexity

### 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.

grokking algorithm go pattern two-pointer