Two Sum - Pair sum in sorted array

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

Examples:

Input: arr[] = {2, 7, 11, 15}, target = 9
Output: 1 2
Explanation: Since the array is 1-indexed, arr[1] + arr[2] = 2 + 7 = 9

Input: {1, 3, 4, 6, 8, 11} target = 10
Output: 3 4
Explanation: Since the array is 1-indexed, arr[3] + arr[5] = 4 + 6 = 10

Approach: To solve the problem, follow the below idea:

The problem can be solved using two pointers technique. We can maintain two pointers, left = 0 and right = n - 1, and calculate their sum S = arr[left] + arr[right].

• If S = target, then return left and right.
• If S < target, then we need to increase sum S, so we will increment left = left + 1.
• If S > target, then we need to decrease sum S, so we will decrement right = right - 1.

If at any point left >= right, then no pair with sum = target is found.

Step-by-step algorithm:

• We need to initialize two pointers as left and right with position at the beginning and at the end of the array respectively.
• Need to calculate the sum of the elements in the array at these two positions of the pointers.
• If the sum equals to target value, return the 1-indexed positions of the two elements.
• If the sum comes out to be less than the target, move the left pointer to the right to the increase the sum.
• If the sum is greater than the target, move the right pointer to the left to decrease the sum.
• Repeat the following steps till both the pointers meet.

Below is the implementation of the algorithm:

#include <vector> using namespace std; vector<int> twoSum(vector<int>& numbers, int target) {  int left = 0, right = numbers.size() - 1;  while (left < right) {  int current_sum = numbers[left] + numbers[right];  // If current sum = target, return left and right  if (current_sum == target) {  return { left + 1, right + 1 };  }  // If current sum < target, then increase the  // current sum by moving the left pointer by 1  else if (current_sum < target) {  left++;  }  else {  // If current sum > target, then decrease the  // current sum by moving the right pointer by 1  right--;  }  }  return {}; } // Example usage #include <iostream> int main() {  vector<int> numbers = { 2, 7, 11, 15 };  int target = 9;  vector<int> result = twoSum(numbers, target);  for (int num : result) {  cout << num << " ";  }  cout << endl;  return 0; } // This code is contributed by Shivam Gupta 

import java.util.*; public class TwoSum {  public static List<Integer> twoSum(List<Integer> numbers, int target) {  int left = 0, right = numbers.size() - 1;  while (left < right) {  int current_sum = numbers.get(left) + numbers.get(right);  // If current sum = target, return left and right  if (current_sum == target) {  return Arrays.asList(left + 1, right + 1);  }  // If current sum < target, then increase the  // current sum by moving the left pointer by 1  else if (current_sum < target) {  left++;  } else {  // If current sum > target, then decrease the  // current sum by moving the right pointer by 1  right--;  }  }  return Collections.emptyList();  }  public static void main(String[] args) {  List<Integer> numbers = Arrays.asList(2, 7, 11, 15);  int target = 9;  List<Integer> result = twoSum(numbers, target);  for (int num : result) {  System.out.print(num + " ");  }  System.out.println();  } } // This code is contributed by Ayush Mishra 

def twoSum(numbers, target): left, right = 0, len(numbers) - 1 while left < right: current_sum = numbers[left] + numbers[right] # If current sum = target, return left and right if current_sum == target: return [left + 1, right + 1] # If current sum < target, then increase the current sum by moving the left  # pointer by 1 elif current_sum < target: left += 1 else: # If current sum > target, then decrease the current sum by  # moving the right pointer by 1 right -= 1 return [] # Example usage numbers = [2, 7, 11, 15] target = 9 print(twoSum(numbers, target)) 

// Function to find two numbers such that they add up to a specific target function twoSum(numbers, target) {  let left = 0;  let right = numbers.length - 1;  // Continue searching while the left index is less than the right index  while (left < right) {  let currentSum = numbers[left] + numbers[right];    // If the current sum equals the target, return the indices (1-indexed)  if (currentSum === target) {  return [left + 1, right + 1];  }  // If the current sum is less than the target, move the left index to the right  else if (currentSum < target) {  left++;  }  // If the current sum is greater than the target, move the right index to the left  else {  right--;  }  }  // Return an empty array if no two numbers sum up to the target  return []; } const numbers = [2, 7, 11, 15]; const target = 9; const result = twoSum(numbers, target); // Output the result result.forEach(num => {  console.log(num); }); 

[1, 2] 

Time Complexity: O(n), where n is declared to be as length of array because elements of array is traced only once.
Auxiliary Space: O(1)