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. Your task is to return the indices of the two numbers (i.e. the pair) such that they add up to the given target.
Example:
Input: arr: [1, 2, 3, 4, 6], target: 6 Output: [1, 3] Explanation: At index 1, we have 2 and at index 3, we have 4. Hence, arr[1] and arr[3] adds up to give 6 as a target sum.
Code
Java
C++
Python
class Innoskrit {
public static int[] targetSum(int arr[], int target) {
int left = 0, right = arr.length - 1;
while(left < right) {
int sum = arr[left] + arr[right];
if(sum == target) {
return new int[] {left, right};
}
if(target > sum) {
left++;
} else {
right--;
}
}
return new int[] {-1, -1};
}
public static void main(String[] args) {
int arr[] = new int[] {1, 2, 3, 4, 6};
int target = 6;
int ans[] = Innoskrit.targetSum(arr, target);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
}
}
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static pair<int, int> targetSum(const vector<int> &arr, int target) {
int left = 0, right = arr.size() - 1;
while(left < right) {
int sum = arr[left] + arr[right];
if(sum == target) {
return make_pair(left, right);
}
if(target > sum) {
left++;
} else {
right--;
}
}
return make_pair(-1, -1);
}
};
int main() {
vector<int> arr = {1, 2, 3, 4, 6};
int target = 6;
pair<int, int> ans = Innoskrit::targetSum(arr, target);
cout << "[" << ans.first << ", " << ans.second << "]";
return 0;
}
class Innoskrit:
@staticmethod
def target_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
sum = arr[left] + arr[right]
if sum == target:
return [left, right]
if target > sum:
left += 1
else:
right -= 1
return [-1, -1]
if __name__ == '__main__':
arr = [1, 2, 3, 4, 6]
target = 6
ans = Innoskrit.target_sum(arr, target)
print(ans)
Output:
[1, 3]
Time and Space Complexity
Time Complexity: O(N)
Space Complexity: O(1)