LeetCode Solutions explained using Python: #1

Two Sum:

• Read the problem

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.

Intuition part 1:

We need to find two indices in an array that add up to a certain target, we can initially try to brute force the solution by iterating over every single number in the array, then searching through every other number and trying to see if any of them add up to the target:

twoSum(nums, target):
for i in range from 0 to length of nums
  for j in range of 0 to length of nums
    if i does not equal j
      if nums[i] + nums[j] is equal to the target
        return [i, j]

This is too inefficient, because the time complexity of this solution is O(n²). If this solution doesn’t work, what can we try?

• Hash maps have an query time complexity of O(1), which is low enough to work for this problem. Creating a hash map is tricky though (especially in Python where dictionaries do not have .get() methods like in Java!). We need to find the indices associated with the numbers that will add up to the target, not the numbers themselves!

Since hash maps are implemented as dictionaries in Python, this implies that we need to create a dictionary where when we access a value in the dictionary it will return the index associated with a certain number in the array, not the number itself.

We can do this, by setting the key in a <K, V> pair as a number associated with an index in the original array which means when we use the subscript method ([] in Python), it will return the index as the value. We can do this by setting the index as the value:

• Set[nums[index]] = index

Intuition Part 2:

We still need to search through every number in the array and find if there is another number that when combined with the current number will equal the target.

This is the initial part of the solution:

twoSum(nums, target)
set = {}
for i in range from 0 to length of nums
  targetValue = target - nums[i]

The set is initialized and we create a target value for each number in the array (this is the value that must be added to the number to equal to the target). What else do we need to do?

twoSum(nums, target)
set = {}
for i in range from 0 to length of nums
  targetValue = target - nums[i]
  if targetValue in set
    return [i, set[targetValue]]

We still need to update the set, because we are trying to find the target value in the set, the solution will not work without adding the target value to the set!

twoSum(nums, target)
set = {}
for i in range from 0 to length of nums
  targetValue = target - nums[i]
  if targetValue in set
    return [i, set[targetValue]]
  else
    set[nums[i]] = i
return [-1,-1]

By adding the target value to the set every time we iterate, we ensure that we can get the index if the target value is in the array somewhere. If we don’t find any numbers that work, return [-1, -1]

Here is the full Python solution:

class Solution:
  def twoSum(self, nums, target):
    set = {}
    for i in range(len(nums)):
      targetValue = target - nums[i]
      if targetValue in set:
        return [i, set[targetValue]]
      else:
        set[nums[i]] = i
    return [-1,-1]

Common mistakes:

• Many times people will forget that the target value is not meant to be added to the set, it’s actually meant to be checked if the target value equal to a value in the set. The target value is meant to be another number in the array.
• This means that the line after the else statement near the end of the loop should not be set[targetValue] = i, but rather set[nums[i]] = i.