Table of contents
Open Table of contents
Problem
Given a 1indexed array of integers numbers
that is already sorted in nondecreasing 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
, as an integer array [index1, index2]
of length 2. The solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Constraints:
2 <= numbers.length <= 3 * 10^4
1000 <= numbers[i] <= 1000
numbers
is sorted in nondecreasing order.1000 <= target <= 1000
 The tests are generated such that there is exactly one solution.
Explanation/Approach
Two Pointer Approach:
 Two Pointers: Start with two pointers, one at the beginning (
left
) and one at the end (right
) of the array.  Moving the Pointers: If the sum of
numbers[left]
andnumbers[right]
is less than the target, move theleft
pointer to the right. If the sum is greater, move theright
pointer to the left.  Finding the Solution: When the sum equals the target, return the indices of these two numbers.
Solution: Two Pointers
class Solution:
def twoSum(self, numbers: List[int], target: int) > List[int]:
left, right = 0, len(numbers)  1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
# Add 1 to each index because the array is 1indexed
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right = 1
# Since there is exactly one solution, this return is theoretically unreachable
return [1, 1]
Time and Memory Complexity
The time complexity is O(n), where n is the number of elements in numbers
, as each element is visited at most once. The space complexity is O(1), as only two pointers are used.
Explanation
The twopointer approach efficiently finds the two numbers that sum up to the target. We move the left
pointer to the right to increase the sum and the right
pointer to the left to decrease the sum. This method leverages the sorted nature of the array to find the solution in a linear scan.
Visual Representation
Consider the input numbers = [2,7,11,15]
and target = 9
.

Initial Pointers:
left = 0
(pointing to 2) andright = 3
(pointing to 15).

Iteration Steps:
 First iteration: Sum of
2 + 15 = 17
(greater than 9), moveright
to the left.  Second iteration:
left = 0
(2) andright = 2
(11). Sum =2 + 11 = 13
(greater than 9), moveright
to the left.  Third iteration:
left = 0
(2) andright = 1
(7). Sum =2 + 7 = 9
(equals target), return[1, 2]
.
 First iteration: Sum of
Iteration 1: [2, 7, 11, 15]
^ ^
left right
Iteration 2: [2, 7, 11, 15]
^ ^
left right
Iteration 3: [2, 7, 11, 15]
^ ^
left right
In each iteration, we adjust the pointers based on the sum compared to the target, leading us to the solution.
Solution: Hashmap
 Hashmap for Complement: Use a hashmap to store the complement of each number with respect to the target, along with its index.
 Iterating Through the Array: For each number, check if it’s already in the hashmap. If it is, it means we have found the pair that adds up to the target.
 Returning Indices: Once a pair is found, return the indices of these two numbers.
class Solution:
def twoSum(self, numbers: List[int], target: int) > List[int]:
hashmap = {}
for i, num in enumerate(numbers):
if num in hashmap:
# The array is 1indexed, so add 1 to the indices
return [hashmap[num] + 1, i + 1]
# Store the complement and its index
hashmap[target  num] = i
# Since there is exactly one solution, this return is theoretically unreachable
return [1, 1]
Time and Memory Complexity
The time complexity is O(n), where n is the number of elements in numbers
, as we iterate through the array once. The space complexity is O(n), due to the additional hashmap storing up to n elements.
Explanation
In this approach, we use a hashmap to store the complement of each number with respect to the target. As we iterate through the array, we check if the current number exists in the hashmap. If it does, it means we have found the two numbers that sum up to the target. The indices of these two numbers are then returned.
Visual Representation
Consider the input numbers = [2,7,11,15]
and target = 9
.

Building the Hashmap:
 Start iterating through
numbers
.  For 2, store
7
(complement of 9  2) with index0
.  For 7, find it already exists in the hashmap.
 Start iterating through

Finding the Pair:
 Upon finding 7 in the hashmap, we know that 2 (at index 0) and 7 (current index) are the required pair.
numbers = [2, 7, 11, 15], target = 9
Hashmap Status:
{2: 0} # Complement of 2 stored with its index
Finding 2 in the hashmap indicates the pair (2, 7) that sums up to 9. Indices: [1, 2].
In this way, the hashmap approach efficiently finds the two numbers that sum up to the target in a single pass through the array.