LeetCode #1 in Python and Go

LeetCode is a social programming platform that lets developers improve their problem solving skills while preparing for technical interviews. Some companies pull content directly from LeetCode for coding interviews, others will create more relevant work-sample-problems to challenge you. But either way, LeetCode can be a fun way to learn data structures and algorithms.

The questions and contests are organized by difficulty. They can be solved by typing into LeetCode’s online editor with your language of choice. Your solution is then ranked by runtime speed and memory usage.

The platform has a free plan that lets you solve a lot of problems. They also have a subscription plan that unlocks premium features like more questions, detailed solutions, interview simulations, and interview questions from companies like Google and Microsoft.

In this post, we look at the Two Sum problem with Python and Go.

Two Sum

The description of the Two Sum problem is shown below:

Example Results

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

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

The fact that each input has one and only one solution makes this a relatively easy problem to solve, and it’s a problem that can be solved in two ways.

Python

Python contains a function called enumerate() that receives an iterable and returns an iteration counter and the value for each element of a list when used with a for loop.

enumerate() technically doesn’t return the index of the value. It’s just a counter integer that starts at 0 and increments for each element. The function allows you to start the counter at any number you wish. For example, pass an int to the start parameter using the syntax enumerate(iterable, start=2) to start the counter at 2.

Solution 1

The first solution is the “brute-force” method in which we iterate over all the elements in the list with one loop, then iterate over the remaining elements with a nested loop, checking if there are two values that sum to the target integer.

The pseudocode for this method is shown below:

loop over elements in the nums list
  loop over elements in the nums list starting with the next indice
    if elements sum to target value
      return indices

We can update our pseudocode with Python and get something like the following.

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    for index, value in enumerate(nums):
      for index2, value2 in enumerate(nums[index+1:], index+1):
        if value + value2 == target:
          return [index, index2]

The first for loop enumerates over all the elements in the list while assigning the index and value to the corresponding variables.

The second loop also enumerates over the elements and assigns the values to index2 and value2. However, we slice the nums array using [index+1:] to remove the current and any previous elements from the list. This lets us just check wether the sum of the value at the current index plus any remaining elements equals our target value.

We also set the counter parameter to start at our current index plus 1 to represent where we are beginning this iteration from in the nums list.

Finally, we compare the sum of value1 and value2 to the target and return the index values if a match is made.

The runtime we get for this solution is 4,349 ms. In computer time, it’s a little on the slow side.

Solution 2

A more elegant solution for the Two Sum problem is to use a dictionary instead. We can store value-indices in a dictionary as key-value pairs. This results in a much quicker lookup time.

The pseudocode for this method is shown below:

create a dictionary

loop over elements in the nums list
  if the difference between target and current value is a key in the dictionary
    return the current index and the dictionary value
  set a dictionary key for value to be the index of the value

Convert the pseudocode to Python and we get something like:

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    index_dict = {}
  
    for index, value in enumerate(nums):
      if target-value in index_dict:
        return [index, index_dict[target-value]]
      else:
        index_dict[value] = index

We first create an empty dictionary called index_dict.

Then we loop over our list using the enumerate() function, setting values for index and value.

We check if the difference between target and value exists in our dictionary as a key and if it does, we return the current iteration index and the value of the target-value key in the dictionary.

If the value doesn’t exist in the dictionary, we create a new key and set the value equal to the iteration’s index value.

For a list [2,7,11,15], the code would produce a dictionary like:

{  2: 0,
   7: 1,
  11: 2,
  15: 3 }

If the target is 9, we are essentially just checking if 2 or 7 exists. This greatly simplifies the algorithm.

The runtime we get for this solution is 146 ms.

Go

For fun, we can rewrite the Python solution in Go and use the same approach. The Go syntax looks a little different than Python but the logic is exactly the same.

func twoSum(nums []int, target int) []int {
  numMap := make(map[int]int)

  for index, value := range nums {
    diff := target - value

    if _, ok := numMap[diff]; ok {
      return []int{numMap[diff], index}
    }
    numMap[value] = index
  }

  return []int{}
}

The function twoSum() receives a nums slice of integers and a target integer. It returns a slice of integers, which in our case is just the indices for our two values.

The Go equivalent of a dictionary is a map. We initialize numMap using the make() function.

A for loop is created to loop through the elements of the num slice. With each iteration we set the variable diff equal to the difference between the target and current element value.

The if statement checks whether the diff key is in the map and if it is, returns the current index and the value at the diff index in our map. Otherwise, add the value as a key in the map and set it equal to the current index.

We return an empty map at the end of the function because Go will not compile without a return statement. This is a technicality. We could structure our code differently to prevent the extra return.

Because Go is a compiled language, this program runs faster than Python.

The runtime we get for the Go solution is 2 ms, which is a dramatic improvement over our first Python solution!

Summary

In this post we introduced LeetCode and how to solve the Two Sum problem using Python and Go. In future lessons, we’ll explore more problem solving on the LeetCode platform with these two great languages.