Two-Sum

Patrick Leaton
Published: Feb. 22, 2021, 5:31 p.m.
Problem Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

 

The description was taken from https://leetcode.com/problems/two-sum/.

Problem Solution

#O(N) Time, O(N) Space
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for index, value in enumerate(nums):
            complement = target-value
            if complement in seen:
                return [seen[complement], index]
            else:
                seen[value] = index
               
 

Problem Explanation

The brute force method for solving this problem would be to have a nested loop traversing the array.  We would compare each index of the inner loop with each index of the outer for loop, searching for two numbers that summed to the target value. If we found the two numbers, we would return both indices.  This algorithm would require a quadratic time complexity. 

Instead, what we can do is store the index of each value in a hashmap, so if we come across the second value that we would be able to sum and get the target, we will have its index in constant retrieval.

Let's initialize our hashmap.  For our key, value pairs, we will store each value as the key, and each index as the key's value.

        seen = {}

 

 We will also want to use the enumerate function for traversing the values in nums so that we can keep track of each index. 

        for index, value in enumerate(nums):

 

The solution we are looking for is x+y=target.

If we want to solve for y, we will rearrange this to y = target-x, y being the complement, target being the target number we’re trying to sum up to, and value being the element's value in our current iteration.   

            complement = target-value

 

In each iteration, if we find the complement in our dictionary then we are going to return the complement's index value and our current index. 

            if complement in seen:
                return [seen[complement], index]

 

If we haven't found the second number yet that we be can sum to the target, we will continue to add each number to the dictionary with its index.

            else:
                seen[value] = index

 

In the worst case, we'll need to traverse the entire array and store every value, this yields linear time and linear space.

 

Additional Notes

If the problem requires knowing where other elements are in a data structure, consider storing them in a hashmap.