In this chapter, we will learn how to solve Pair with Target Sum problem using two pointers technique.
Table Of Contents
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: arr: [1, 3, 5, 6, 8, 9], targetSum = 11
Output: [1, 4]
Explanation: The numbers at index 1 and 4 add up to 11: 3 + 8 = 11Example 2:
Input: arr: [1, 2, 3, 4, 6], targetSum = 6
Output: [1, 3]
Explanation: The numbers at index 1 and 3 add up to 6: 2 + 4 = 6Solution:
The brute force solution to this problem is to use two pointers, let’s call them i & j, i starts from 0 and cover all the elements till the second last index of the array. For each i , j will start from i + 1, and finds whether there is any pair that fulfills arr[i] + arr[j] = targetSum. If at any point in time we find a pair that add up to the targetSum, we return a pair of indices otherwise if we fail to find such a pair, we return [-1, -1]. Here is the implementation of the brute force solution:
Java
Python
C++
import java.io.*;
class Innoskrit {
public static int[] findPair(int arr[], int targetSum) {
for(int i = 0; i < arr.length - 1; i++) {
for(int j = i + 1; j < arr.length; j++) {
int sum = arr[i] + arr[j];
if(sum == targetSum) {
return new int[] {i, j};
}
}
}
return new int[] {-1, -1};
}
public static void main (String[] args) {
int ans[] = Innoskrit.findPair(new int[] {1, 3, 5, 6, 8, 9}, 11);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
ans = Innoskrit.findPair(new int[] {1, 2, 3, 4, 6}, 14);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
}
}class Innoskrit:
def find_pair(arr, targetSum):
for i in range(len(arr) - 1):
for j in range(i + 1, len(arr)):
sum = arr[i] + arr[j]
if sum == targetSum:
return [i, j]
return [-1, -1]
if __name__ == '__main__':
ans = Innoskrit.find_pair([1, 3, 5, 6, 8, 9], 11)
print(ans)
ans = Innoskrit.find_pair([1, 2, 3, 4, 6], 14)
print(ans)
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static pair<int, int> findPair(const vector<int> &arr, int targetSum) {
for(int i = 0; i < arr.size() - 1; i++) {
for(int j = i + 1; j < arr.size(); j++) {
int sum = arr[i] + arr[j];
if(sum == targetSum) {
return make_pair(i, j);
}
}
}
return make_pair(-1, -1);
}
};
int main(int argc, char *argv[]) {
auto result = Innoskrit::findPair(vector<int>{1, 3, 5, 6, 8, 9}, 11);
cout << "[" << result.first << ", " << result.second << "]" << endl;
result = Innoskrit::findPair(vector<int>{1, 2, 3, 4, 6}, 14);
cout << "[" << result.first << ", " << result.second << "]" << endl;
}The Time Complexity for the above solution is O(N2). We can reduce it further. Here is how?
Since the given array is sorted, another brute-force solution could be to iterate through the array, taking one number at a time and searching for the second number through Binary Search. The time complexity of this algorithm will be O(N*logN). Can we do better than this?
We can follow the Two Pointers approach. We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair; otherwise, we will do one of two things:
- If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
- If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.
Here is the visual representation of this algorithm for Example-1:
Our algorithm will look like this:
Code:
Java
Python
C++
import java.io.*;
class Innoskrit {
public static int[] findPair(int arr[], int targetSum) {
int start = 0, end = arr.length - 1;
while(start < end) {
int sum = arr[start] + arr[end];
if(sum == targetSum) {
return new int[] {start, end};
}
if(targetSum > sum) {
start += 1;
} else {
end -= 1;
}
}
return new int[] {-1, -1};
}
public static void main(String[] args) {
int ans[] = Innoskrit.findPair(new int[] {1, 3, 5, 6, 8, 9}, 11);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
ans = Innoskrit.findPair(new int[] {1, 2, 3, 4, 6}, 14);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
}
}class Innoskrit:
def find_pair(arr, targetSum):
start, end = 0, len(arr) - 1
while start < end:
sum = arr[start] + arr[end]
if sum == targetSum:
return [start, end]
if targetSum > sum:
start += 1
else:
end -= 1
return [-1, -1]
if __name__ == '__main__':
ans = Innoskrit.find_pair([1, 3, 5, 6, 8, 9], 11)
print(ans)
ans = Innoskrit.find_pair([1, 2, 3, 4, 6], 14)
print(ans)#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static pair<int, int> findPair(const vector<int> &arr, int targetSum) {
int start = 0, end = arr.size() - 1;
while(start < end) {
int sum = arr[start] + arr[end];
if(sum == targetSum) {
return make_pair(start, end);
}
if(targetSum > sum) {
start += 1;
} else {
end -= 1;
}
}
return make_pair(-1, -1);
}
};
int main(int argc, char *argv[]) {
auto result = Innoskrit::findPair(vector<int>{1, 3, 5, 6, 8, 9}, 11);
cout << "[" << result.first << ", " << result.second << "]" << endl;
result = Innoskrit::findPair(vector<int>{1, 2, 3, 4, 6}, 14);
cout << "[" << result.first << ", " << result.second << "]" << endl;
}Output:
[1, 4]
[-1, -1]Time Complexity:
The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.
Space Complexity:
The algorithm runs in constant space O(1).
Innoskrit
We're building a next-level EdTech Startup.
