Easy: Pair with Target Sum

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

Try it yourself

package main
import (
	"reflect"
	"testing"
)
func PairTargetSum(input []int, x int) []int {
  // add your code here
	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

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

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.