< Back




1. Two Sum

Classic question. We maintain a dictionary of the numbers we've encountered so far, with the value of
each key being the index of the number in the array. As we iterarte through the array, we find the
difference between the target value and the current number being inspected. If this difference is a
key in the dictionary, we return the index of that number and the index of the current number.

Without using this dictionary of seen values, we would have to iterate through the array for each
number, resulting in an O(n^2) solution.

The solution is as follows:


  class Solution:
      def twoSum(self, nums: List[int], target: int) -> List[int]:
          diffs = {}

          for i, num in enumerate(nums):
              diff = target - num

              if diff in diffs:
                  return [diffs[diff], i]

              diffs[num] = i


_ Time Complexity:

  O(n) - We iterate through the array once.

_ Space Complexity:

  O(n) - We store at most n values in the dictionary.