# Leetcode Problem 167: Two Sum II - Input Array Is Sorted

Problem description:

Given a 1-indexed array of integers

`numbers`

that is alreadysorted 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 oneas an integer array`[index1, index2]`

of length 2.The tests are generated such that there is

exactly one solution. Youmay notuse the same element twice.Your 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]. Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].`

Constraints:

- 2 <= numbers.length <= 3 * $ 10^4 $
- -1000 <= numbers[i] <= 1000
- numbers is sorted in non-decreasing order.
- -1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.

This is one of those exercise where not reading the problem description will come back to bite you. As usual, laziness is king, so I didn’t bother reading the entire description and went straight into coding. I just copy & pasted the original variant of this exercise, and increased the indices by one.

### (Attempted) brute force Python solution Link to heading

```
# leetcode_167.py
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
n = len(numbers)
for i in range(0, n):
for j in range(i + 1, n):
if numbers[j] + numbers[i] == target:
return [i + 1, j + 1]
```

and was greeted with:

```
Time Limit Exceeded
```

At this point you’re probably thinking I deserve it, and you’d be right in thinking that!

So I went back to reading the problem description to see if there was any useful info. and realised that the fact that the input list is non-decreasing in order, means that it needs to somehow be exploited in the solution. The other important fact is that the exercise guarantees exactly one solution per test case. And finally, that we can create data structures only in $ O(1)$ space.

Armed with this knowledge, I made another attempt.

### Slightly more clever attempt Link to heading

```
# leetcode_167.py
# This is faster than before but still exceeds time limit
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
n = len(numbers)
i = 0
while i < n:
a = numbers[i]
b = target - a
if b in numbers:
j = numbers.index(b, i + 1)
return [i + 1, j + 1]
else:
i += 1
```

and was greeted again with:

```
Time Limit Exceeded
```

The nested `index()`

runs by itself in $ O(n)$, then, inside the lookup operation in
`if b in numbers`

, which also runs in $ O(n)$, both will be $ O(n^2)$… ouch! That’s not
even counting the outer loop, which would also run in $ O(n)$, so potentially $ O(n^3)$.

The solution would strictly have to be $ O(n) $ or better. The solution I came up with uses one loop and two indices that act like “pointers”.

### Solution Link to heading

```
# leetcode_167.py
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
n = len(numbers)
i = 0 # left index
j = n - 1 # right index
# The core idea is to leverage to the max. the fact that the input list
# is already sorted in non-decreasing order.
#
# One way of exploiting that is traversing the list from right to left
# and then gradually reducing the upper_bound, aka right-most index j
# as we check for the condition:
#
# nums[j] + sentinel > target
while j > -1:
# sentinel will be the left-most elem
sentinel = numbers[i]
current = numbers[j]
if current + sentinel > target:
# reduce upper_bound j
j -= 1
elif current + sentinel == target:
# we have our solution indices
return [i + 1, j + 1]
elif current + sentinel < target:
# retain current j but move i one position to the right
i += 1
```

##### Python statistics Link to heading

```
Runtime: 161 ms - beats 58.76% of python3 submissions.
Memory Usage: 14.8 MB - beats 89.38% of python3 submissions.
```

##### Complexity analysis Link to heading

Time: $ O(n) $, because of the loop.

Space: $ O(1) $ because the size of the solution array is always two regardless of input size.

Share on: