Solution

Since the given array is sorted, a 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?

To solve this problem, we can use a two-pointer approach. This approach is efficient because it takes advantage of the sorted nature of the array. By starting with one pointer at the beginning and the other at the end, we can adjust their positions based on the sum of the elements they point to. This allows us to find the pair that adds up to the target without needing to check all possible pairs, which saves time.

By moving the pointers inward, we can systematically find the pair in a single pass through the array. This ensures that the solution is both time-efficient and easy to implement.

Step-by-Step Algorithm

• Initialize two pointers: Start with one pointer (left) at the beginning (index 0) and the other pointer (right) at the end (last index) of the array.
• Loop until pointers meet: Continue the loop until left is less than right.
  • Calculate current sum: Add the elements at the left and right pointers.
  • Check if the sum matches the target:
    • If currentSum equals the target sum, return the indices [left, right].
    • If currentSum is less than the target sum, increment the left pointer to increase the sum.
    • If currentSum is more than the target sum, decrement the right pointer to decrease the sum.
• Return default values: If no pair is found, return [-1, -1].

Algorithm Walkthrough

Let's walk through the example with input [1, 2, 3, 4, 6] and target 6.

• Initialize pointers: left = 0, right = 4
• First iteration:
  • currentSum = 1 + 6 = 7 (greater than target)
  • Decrement right to 3
• Second iteration:
  • currentSum = 1 + 4 = 5 (less than target)
  • Increment left to 1
• Third iteration:
  • currentSum = 2 + 4 = 6 (equals target)
  • Return indices [1, 3]

Here is the visual representation of this algorithm for Example-1:

Time Complexity

1. Initialization: Constant time, O(1), as it involves assigning values to left and right.

2. While Loop:

   • The while loop runs as long as left is less than right.
   • 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 with targetSum, and then incrementing left or decrementing right.

   Therefore, the loop runs in O(n) time, where n is the number of elements in the array.

3. 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, and currentSum.
• 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 two-pointer 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.

Step-by-step Algorithm

1. Initialize a HashMap:

   • Create a HashMap to store numbers as keys and their indices as values.

2. Iterate through the array:

   • Loop through each element in the array using a for loop.

3. Check for the complement:

   • For each element, check if the HashMap contains the complement (i.e., targetSum - current element).
   • If it does, return the indices of the complement and the current element.

4. Store the element and its index:

   • If the complement is not found, store the current element and its index in the HashMap.

5. Return result:

   • If no pair is found by the end of the loop, return [-1, -1].

Algorithm Walkthrough

Example Input: [1, 2, 3, 4, 6], Target: 6

1. Initialize:

   • nums = {}

2. First iteration (i = 0):

   • Current element: 1
   • Complement needed: 6 - 1 = 5
   • 5 is not in nums
   • Store 1 with index 0: nums = {1: 0}

3. Second iteration (i = 1):

   • Current element: 2
   • Complement needed: 6 - 2 = 4
   • 4 is not in nums
   • Store 2 with index 1: nums = {1: 0, 2: 1}

4. Third iteration (i = 2):

   • Current element: 3
   • Complement needed: 6 - 3 = 3
   • 3 is not in nums
   • Store 3 with index 2: nums = {1: 0, 2: 1, 3: 2}

5. Fourth iteration (i = 3):

   • Current element: 4
   • Complement needed: 6 - 4 = 2
   • 2 is in nums with index 1
   • Return indices [1, 3]

Code