0% completed
Problem Statement
Given an array of numbers sorted in ascending order and a target sum, find a pair in the array whose sum is equal to the given target. If no such pair exists return [1, 1].
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
Constraints:
2 <= arr.length <= 104
109 <= arr[i] <= 109
109 <= target <= 109
 Only
one
valid answer exists.
Solution
Since the given array is sorted, a bruteforce 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 endpointer.
 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 startpointer.
Here is the visual representation of this algorithm for Example1:
Code
Here is what our algorithm will look like:
Time Complexity

Initialization: Constant time, O(1), as it involves assigning values to
left
andright
. 
While Loop:
 The
while
loop runs as long asleft
is less thanright
.  In the worst case, this loop iterates over all elements of the array once. This happens when no pair is found, or the pair is found at the extreme ends of the array.
 Each iteration involves a constant amount of work: calculating
currentSum
, comparing it withtargetSum
, and then incrementingleft
or decrementingright
.
Therefore, the loop runs in O(n) time, where n is the number of elements in the array.
 The

Overall: The dominant factor in this algorithm is the while loop, making the overall time complexity O(n).
Space Complexity
 The algorithm uses a fixed amount of extra space: variables
left
,right
, andcurrentSum
.  It does not depend on the size of the input array, as no additional data structures are used that grow with the input size.
 Thus, the space complexity is O(1), constant space.
In summary, the algorithm has a time complexity of O(n) and a space complexity of O(1).
An Alternate approach
Instead of using a twopointer or a binary search approach, we can utilize a HashTable to search for the required pair. We can iterate through the array one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ such that “X+Y==Target”. We will do two things here:
Search for ‘Y’ (which is equivalent to “Target−X”) in the HashTable. If it is there, we have found the required pair. Otherwise, insert “X” in the HashTable, so that we can search it for the later numbers. Here is what our algorithm will look like:
Time Complexity

HashMap Initialization: Constant time, (O(1)).

For Loop:
 The
for
loop iterates over each element of the array once.  In each iteration, the algorithm checks if the element is already present in the
HashMap
(ordictionary
in Python) and either returns a result or inserts an element into theHashMap
.  This element checking or insertion operations of a
HashMap
generally operate in (O(1)) time due to efficient hashing. However, in the worst case (e.g., when many hash collisions occur), these operations can degrade to (O(n)). Under the assumption of a good hash function with minimal collisions, these operations can be considered (O(1)).
Therefore, the loop runs in (O(n)) time in the average case, where (n) is the number of elements in the array.
 The

Overall: The dominating factor in this algorithm is the for loop. Under the assumption of efficient hashing, the overall average time complexity is (O(n)).
Space Complexity
 The algorithm uses a
HashMap
to store elements from the array. In the worst case, this map can store all elements of the array if no pair is found that adds up to the target sum  Thus, the space complexity is proportional to the number of elements in the array, which is (O(n)).
In summary, the algorithm has an average time complexity of (O(n)) and a space complexity of (O(n)). The time complexity can degrade to (O(n^2)) in the worst case due to potential hash collisions, but this is generally not the common case with a good hash function.