LeetCode 167: Two Sum II - Input Array Is Sorted

Problem Description

Difficulty: Medium

Given an array of integers numbers that is sorted in non-decreasing order.

Return the 1-indexed indices of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal; therefore, you may not use the same element twice.

There will always be exactly one valid solution.

The solution must use \(O(1)\) additional space.

Example 1:

Input: numbers = [1,2,3,4], target = 3
Output: [1,2]

Explanation:
The sum of 1 and 2 is 3. Assuming a 1-indexed array, we return [1, 2].

Example 2:

Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints:

2 <= numbers.length <= 1000
-1000 <= numbers[i] <= 1000
-1000 <= target <= 1000
numbers is sorted in increasing order

Initial Solution(s)

This seems to be the same problem as Leetcode problem #1 (Two Sum) but with a 1-indexed array instead of a 0-indexed array. I just added + 1 into the old solution and it passed all the tests. Perhaps I’m missing something…

from typing import List

class InitialSolution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(numbers):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff] + 1, i + 1]
            prevMap[n] = i

So, yes, I was missing something! I missed the instruction saying “Your solution must use \(O(1)\) additional space.” The hashmap would use \(O(n)\) additional space in the worst case. NeetCode has this problem in the two-pointer algorithm category, so let’s try again with that approach.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # define left and right pointers
        l = 0
        r = len(numbers) - 1
        
        while l < r:
            summation = numbers[l] + numbers[r]
            
            if summation > target:
                r -= 1
            elif summation < target:
                l += 1
            else: # since we are told there is always a solution:
                return [l + 1, r + 1]

Test function

def test_two_sum(solution_class):
    """ Test of twoSum function. Not extensive."""
    # Instantiate the class
    solution = solution_class()

    # Define the test cases
    test_cases = [
        {
            "numbers": [2, 3, 4],
            "target": 6,
            "expected": [1, 3]
        },
        {
            "numbers": [1, 2, 3, 4],
            "target": 3,
            "expected": [1, 2]
        },
         {
            "numbers": [2, 3, 4, 5],
            "target": 8,
            "expected": [2, 4]
        },
        {
            "numbers": [-1, 0],
            "target": -1,
            "expected": [1, 2]
        }
    ]
    # Iterate over test cases
    for i, test_case in enumerate(test_cases):
        numbers = test_case["numbers"]
        target = test_case["target"]
        expected = test_case["expected"]
        
        # Get the result from the twoSum method
        results = solution.twoSum(numbers, target)
        
        # Check if the result matches the expected output
        if results == expected:
            print(f"Test case {i+1} passed")
        else:
            print(f"Test case {i+1} failed")
            print(f"Expected: {expected}")
            print(f"Got: {results}")

test_two_sum(InitialSolution)

Test case 1 passed
Test case 2 passed
Test case 3 passed
Test case 4 passed

Initial Results

My solution passed the LeetCode submission with a pretty average score. It beat 49% of submissions on runtime and 40% on memory. The distribution of the latter was very skewed, with the vast majority of submissions using the same amount of memory as my solution. In Big O notation, the space complexity is \(O(1)\) as we only use a constant amount of extra space (the two pointers l and r, and a few other variables). No additional data structures are used that would grow with the input size.

• Time complexity: \(O(n)\)
  
• Additional space complexity: \(O(1)\)

NeetCode Solution

NeetCode’s solution was the same as my solution, but with different variable names. The code is provided above.