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

Problem description:

Given a 1-indexed array of integers numbers that is already sorted 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 one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use 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

Ah shit, here we go again.

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:
LinkedIn