This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

Problem: Given an array, find the two indices that sum to a specific value.

Constraints

  • Is there exactly one solution?
    • Yes
  • Is there always a solution?
    • Yes
  • Is the array an array of ints?
    • Yes
  • Is the array sorted? No
  • Are negative values possible?
    • Yes
  • Can we assume the inputs are valid?
    • No
  • Can we assume this fits memory?
    • Yes

Test Cases

  • None input -> TypeError
  • [] -> ValueError
  • [1, 3, 2, -7, 5], 7 -> [2, 4]

Algorithm

Brute force

  • For i in range(len(input)):
    • For j in range(i+1, len(input)):
      • if i + j == target return True
  • return False

Complexity:

  • Time: O(n^2)
  • Space: O(1)

Optimized

* Loop through each num in nums
    * Calculate the cache_target = target - num

target = 7
index  =  0  1  2   3  4
nums   = [1, 3, 2, -7, 5]
          ^
cache_target = 7 - 1 = 6
cache
6 -> 0

1 not in cache

index  =  0  1  2   3  4
nums   = [1, 3, 2, -7, 5]
             ^
cache_target = 7 - 3 = 4
cache
6 -> 0
4 -> 1

3 not in cache

index  =  0  1  2   3  4
nums   = [1, 3, 2, -7, 5]
                ^
cache_target = 7 - 2 = 5
cache
6 -> 0
4 -> 1
5 -> 2

2 not in cache

index  =  0  1  2   3  4
nums   = [1, 3, 2, -7, 5]
                    ^
cache_target = 7 + 7 = 14
cache
6  -> 0
4  -> 1
5  -> 2
14 -> 3

-7 not in cache

index  =  0  1  2   3  4
nums   = [1, 3, 2, -7, 5]
                       ^
cache_target = 7 - 5 = 2
cache
6  -> 0
4  -> 1
5  -> 2
14 -> 3

5 in cache, success, output matching indices: cache[num] and current iteration index

output = [2, 4]

Complexity:

  • Time: O(n)
  • Space: O(n)

Code

In [1]:
class Solution(object):

    def two_sum(self, nums, target):
        if nums is None or target is None:
            raise TypeError('nums or target cannot be None')
        if not nums:
            raise ValueError('nums cannot be empty')
        cache = {}
        for index, num in enumerate(nums):
            cache_target = target - num
            if num in cache:
                return [cache[num], index]
            else:
                cache[cache_target] = index
        return None

Unit Test

In [2]:
%%writefile test_two_sum.py
import unittest


class TestTwoSum(unittest.TestCase):

    def test_two_sum(self):
        solution = Solution()
        self.assertRaises(TypeError, solution.two_sum, None, None)
        self.assertRaises(ValueError, solution.two_sum, [], 0)
        target = 7
        nums = [1, 3, 2, -7, 5]
        expected = [2, 4]
        self.assertEqual(solution.two_sum(nums, target), expected)
        print('Success: test_two_sum')


def main():
    test = TestTwoSum()
    test.test_two_sum()


if __name__ == '__main__':
    main()
Overwriting test_two_sum.py
In [3]:
%run -i test_two_sum.py
Success: test_two_sum