Two Sum II (via Leetcode)¶

Date published: 2023-05-08

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, lists, two pointers

Problem found on Leetcode.

Problem statement:

Given a list of integers that is sorted in ascending order, find two numbers in the list that add up to a specific target number.

The function should return the indices of the tow numbers such that they add up to the target. The first index returned should be smaller than the next one. For this problem, assume index starts at 1, not traditional zero-based indexing.

There's always exactly one solution.

Desired solution must use constant extra space, meaning an increase in items in nums won't increase space complexity.

Test Cases¶

In [2]:

# assert two_sum(numbers=[0, 3, 5, 9], target=8) == [2, 3]

# assert two_sum(numbers=[0, 3, 5, 9], target=8) == [2, 3]

The sum of 3 and 5 is the target value of 8. Since this is one-based indexing, 3 and 5 are respectively at indices 2 and 3.

In [3]:

# assert two_sum(numbers=[9, 10, 5, 15], target=25) == [2, 4]

# assert two_sum(numbers=[9, 10, 5, 15], target=25) == [2, 4]

In [4]:

# assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

# assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

In [5]:

# assert two_sum(numbers=[0, 0, 3, 4], target=0) == [1, 2]

# assert two_sum(numbers=[0, 0, 3, 4], target=0) == [1, 2]

Solution #1 - the Brute Force Way¶

This solution is not constant extra space; it's O(n) space complexity. This solution would be fine to use in a production application.

Pseudocode¶

In [6]:

# convert numbers list into dict of keys as nums and values as list of indexes (+1 for each index)
# [2,7,11,15] -> {2: [0], 7: [1], 11: [2], 15: [3]} 

# for num, list_indexes in dict:
    # given nums=[2, 0, 2] and target=4, don't use first 2 twice so check target-num != num
    # if target-num != num and target-num in dict:
        # return [list_indexes[0], dict[target-num][0]]

# reach here if no two distinct numbers add up to target
# two of the same number must add up to target
# half = target/2
# return dict[half]

# convert numbers list into dict of keys as nums and values as list of indexes (+1 for each index) # [2,7,11,15] -> {2: [0], 7: [1], 11: [2], 15: [3]} # for num, list_indexes in dict: # given nums=[2, 0, 2] and target=4, don't use first 2 twice so check target-num != num # if target-num != num and target-num in dict: # return [list_indexes[0], dict[target-num][0]] # reach here if no two distinct numbers add up to target # two of the same number must add up to target # half = target/2 # return dict[half]

Code¶

In [7]:

from collections import defaultdict
from typing import List


def two_sum(numbers: List[int], target: int) -> List[int]:

    num_indexes = defaultdict(list)

    # prompt asked for 1-indexing
    for index, num in enumerate(numbers):
        num_indexes[num].append(index+1)

    for num, list_indexes in num_indexes.items():
        difference_num = target - num
        if difference_num != num and difference_num in num_indexes:
            return [list_indexes[0], num_indexes[difference_num][0]]
    # no distinct two numbers may add up to target
    # so there must be two occurrences of a number that is half of target
    half = target / 2
    return num_indexes[half]

from collections import defaultdict from typing import List def two_sum(numbers: List[int], target: int) -> List[int]: num_indexes = defaultdict(list) # prompt asked for 1-indexing for index, num in enumerate(numbers): num_indexes[num].append(index+1) for num, list_indexes in num_indexes.items(): difference_num = target - num if difference_num != num and difference_num in num_indexes: return [list_indexes[0], num_indexes[difference_num][0]] # no distinct two numbers may add up to target # so there must be two occurrences of a number that is half of target half = target / 2 return num_indexes[half]

Complexity¶

Time complexity at worst case is O(2n) which can be simplified to O(n) because there's two iterations over all values in nums.

Space complexity O(n), where n is the length of items in nums. This is because I'm using a defaultdict called num_indexes to store the indices of each number in the input array.

Run Test Cases¶

In [8]:

assert two_sum(numbers=[9, 10, 5, 15], target=20) == [3, 4]

assert two_sum(numbers=[9, 10, 5, 15], target=20) == [3, 4]

In [9]:

assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

In [10]:

assert two_sum(numbers=[0, 0, 3, 4], target=0) == [1, 2]

assert two_sum(numbers=[0, 0, 3, 4], target=0) == [1, 2]

Solution #2 - a More Performant Way¶

Pseudocode¶

This method is more of a Leetcode trick that's doable because nums is sorted. I wouldn't expect someone to code this solution in a production application.

In [15]:

# initialize left_pointer to the first index of the array
# initialize right_pointer to the last index of the array

# while left_pointer is less than right_pointer:
    # calculate the sum of elements at left_pointer and right_pointer (current_sum)
    
    # if current_sum equals the target:
        # return the indices (left_pointer + 1) and (right_pointer + 1) since it's 1-indexed

    # if current_sum is less than the target:
        # try to find larger sum...
        # move left_pointer one step to the right (increment left_pointer)

    # if current_sum is greater than the target:
        # try to find smaller sum...
        # move right_pointer one step to the left (decrement right_pointer)

# no solution is found, return an empty list (although the problem statement guarantees one)

# initialize left_pointer to the first index of the array # initialize right_pointer to the last index of the array # while left_pointer is less than right_pointer: # calculate the sum of elements at left_pointer and right_pointer (current_sum) # if current_sum equals the target: # return the indices (left_pointer + 1) and (right_pointer + 1) since it's 1-indexed # if current_sum is less than the target: # try to find larger sum... # move left_pointer one step to the right (increment left_pointer) # if current_sum is greater than the target: # try to find smaller sum... # move right_pointer one step to the left (decrement right_pointer) # no solution is found, return an empty list (although the problem statement guarantees one)

Code¶

In [16]:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # Initialize two pointers at the beginning and end of the array
        left_index, right_index = 0, len(numbers) - 1

        while left_index < right_index:
            # Calculate the sum of elements at left and right pointers
            current_sum = numbers[left_index] + numbers[right_index]

            if current_sum == target:
                # Return the indices, but remember to add 1 since the problem uses 1-based indexing
                return [left_index + 1, right_index + 1]
            elif current_sum < target:
                # If the current_sum is less than the target, move the left pointer to the right
                left_index += 1
            else:
                # If the current_sum is greater than the target, move the right pointer to the left
                right_index -= 1

class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: # Initialize two pointers at the beginning and end of the array left_index, right_index = 0, len(numbers) - 1 while left_index < right_index: # Calculate the sum of elements at left and right pointers current_sum = numbers[left_index] + numbers[right_index] if current_sum == target: # Return the indices, but remember to add 1 since the problem uses 1-based indexing return [left_index + 1, right_index + 1] elif current_sum < target: # If the current_sum is less than the target, move the left pointer to the right left_index += 1 else: # If the current_sum is greater than the target, move the right pointer to the left right_index -= 1

Complexity¶

Time complexity is at worst cast O(n) because we may increment or decrement each pointer until they both reach the middle of nums.

Space complexity is O(1) because we use a fixed amount of memory to store the two pointers regardless of the size of nums.

Run Test Cases¶

In [17]:

assert two_sum(numbers=[9, 10, 5, 15], target=20) == [3, 4]

assert two_sum(numbers=[9, 10, 5, 15], target=20) == [3, 4]

In [18]:

assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

In [19]:

assert two_sum(numbers=[0, 0, 3, 4], target=0) == [1, 2]

assert two_sum(numbers=[0, 0, 3, 4], target=0) == [1, 2]