TWOSUMARY - Editorial

Problem Link - Two Sum in a Sorted Array

Problem Statement

Given a sorted array of integers, arr, and a target integer, target, the task is to determine if there exists a pair of elements in the array whose sum equals target. If such a pair exists, return any one of them; otherwise, return -1.

Approach

The logic to solve this problem relies on the two-pointer technique, which works efficiently with sorted arrays. The approach involves placing one pointer, left, at the beginning of the array and the other, right, at the end. We then calculate the sum of the elements at these two pointers. If the sum equals the target, we return a success result. If the sum is less than the target, we move the left pointer one step forward to increase the sum. If the sum is greater than the target, we move the right pointer one step backward to decrease the sum. This process continues until a pair is found or the pointers cross each other, indicating no such pair exists.

Time Complexity

The time complexity is O(n) because each pointer moves at most n steps in total.

Space Complexity

The space complexity is O(1) as only a few variables are required.