Table of Content

  1. Problem Statement
  2. Problem Input
  3. Solution

Problem statement

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,


Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Input

class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':

Straightforward solution

Source code

Time Complexity: O(N^2)

Space Complexity: O(1)

So the objective here is go through the given array, nums, and find two numbers inside such that they add up to a given sum. Immediately, we know that we have to iterate through the array. Because we cannot use the same element twice, we need to look for two different elements in the array that adds up to the given target. The easiest way to do this would be to:

  1. Iterate through the array.
  2. Use the current element as one of the two required numbers.
  3. Pick another element as the second number.
  4. Check if the current two elements add up to the target
  5. If they do, return both of their indices in the array and you’re done.
  6. If they don’t, then change one of the two elements.

There’s many ways to implement this, but the standard approach is to utilize a doubled for loop. This approach is easy to understand and is guaranteed to cover all possible 2-combinations of the elements.

  1. The first for loop would start with the 1st element of the array.
  2. The second nested for loop would start with the 2nd element of the array since the 1st element is already in use.
  3. If the two numbers don’t add up to the target, then the nested for loop will choose the next element, e.g the 3rd element
  4. This ensures that we are going through all combinations of the 1st element (first for loop) and every element after it (second for loop).
  5. If we still don’t have two numbers adding up to target, then we start over by going through all combinations of the 2nd element and every element after it.
class Solution:
  def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
    # First for loop start with the first element and iterates until the end.
    for i in range(0, len(nums)):
      # Second for loop takes the next element after the i-th index and iterates until the end.
      for j in range(i + 1, len(nums)):
        # If our two numbers add to target, we just return an array of those two numbers.
        if (nums[i] + nums[j] == target):
          return [i, j]
      # End of the second for loop, meaning the first for loop will start over with the i+1 index.

Complexity Explanation

Because we’re using two for loops and one of them is nested, For every one iteration of the outer for loop, we’re performing an iteration of the entire nested for loop, which is O(N). Because worst case, we also have to perform N iterations for the outer loop, we have to perform N * N iterations, therefore the time complexity is O(N^2).

Since we are not introducing any new data structures, there space complexity is just constant, O(1).

Optimized solution

Source code

Time Complexity: O(N)

Space Complexity: O(N)

The first solution is not ideal as the time complexity is quadratic. However, we can actually remove our nested for loop at the expense of using a hash table as a cache. Given a number, all we care about is if there’s another number that will add up to the target number. We can perform a first pass through the array and store the number and its index as a key value pair in our hash table. Then as we iterate through the array, we can subtract the target from the current number and check if the resulting number exists in our hash table.

class Solution:
  def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
    # Using a hash table as a cache
    cache = {}
    # First pass to fill our cache with <number, index>.
    for i in range(0, len(nums)):
      cache[nums[i]] = i
    # Second pass to check if our cache contains any number that can add up to the target.
    for j in range(0, len(nums)):
      # Performing a simple subtraction to figure out what number we need in the cache.
      leftover = target - nums[j]
      # if the number we need exists and the index of that number is not the same as our current index (because we can't reuse the same element), we're done.
      if (leftover in cache and cache[leftover] != j):
        # order is not important, as long as the returning array contains the two correct indices.
        return [cache[leftover], j]

Complexity Explanation

Because now we’re not using a nested for loop, we’ve effectively reduced our time complexity from O(N^2) down to O(N).

Since we are introducing a hash table, which can store up to N key value pairs for this problem. Our space complexity is now O(N).

Even more optimized Solution

Source code

Time Complexity: O(N)

Space Complexity: O(N)

We can optimize our second solution even further by doing everything in our first pass, effectively eliminating the need for the extra second pass. This approach shares similarity with the sliding window technique.

class Solution:
  def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
    # Using a hash table as a cache
    cache = {}
    # Iterate to check if our cache contains any number that can add up to the target.
    for i in range(0, len(nums)):
      # Performing a simple subtraction to figure out what number we need in the cache.
      leftover = target - nums[i]
      # if the number we need exists and the index of that number is not the same as our current index (because we can't reuse the same element), we're done.
      if (leftover in cache and cache[leftover] != i):
        # order is not important, as long as the returning array contains the two correct indices.
        return [cache[leftover], i]
      else:
        # Fill the cache as we iterate. This works because we essentially are "memorizing" numbers via the cache as we iterate, so we remember all of the old numbers as we check new numbers.
        cache[nums[i]] = i

Complexity Explanation

Even though we managed to reduce the number of for loops from 2 to 1, the time complexity is still O(N)since the constant is ignored in big O notation.

Space complexity stays the same because we’re still using a hash table for the same purpose.