Jovian
⭐️
Sign In
Learn data science and machine learning by building real-world projects on Jovian

Two Sum

In [18]:
project_name = 'twosum'
In [19]:
!pip install jovian --upgrade --quiet
In [20]:
import jovian
In [21]:
jovian.commit(project=project_name)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum

Problem Statement

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.

Source: https://leetcode.com/problems/two-sum/

Solution

Problem

We have to create a function that returns indices of two numbers such that they add upto the target we pass

Input

  1. nums = [2,4,6,8], target = 6
  2. nums = [1,3,5,7], target = 12

(add more if required)

Output

  1. [0,1] 2.[1,3]

(add more if required)


Based on the above, we can now create a signature of our function:

In [5]:
def twosum(nums, target):
    pass
In [6]:
import jovian
In [ ]:
jovian.commit()
In [ ]:
 

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

  1. A general case
  2. An empty list
  3. The target should be the sum of the elements in the two ends
  4. No elements add up to the passed target
  5. The list contains a zero element
In [7]:
test0 = {
    'input': {
        'nums' : [2,4,6,8], 'target' : 6
    },
    'output': [0,1]
}
In [9]:
test1 = {
    'input': {
        'nums' : [], 'target' : 2
    },
    'output': None
}
In [10]:
test2 = {
    'input': {
        'nums' : [1,2,4,6,8,10] , 'target' : 11
    },
    'output': [0,5]
}
In [11]:
test3 = {
    'input': {
        'nums' : [12,15,17,18] , 'target' : 28
    },
    'output': None
}
In [12]:
test4 = {
    'input': {
        'nums' : [0,4,6,2,9] , 'target' : 9
    },
    'output': [0,4]
}

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [13]:
tests = [test0, test1, test2, test3, test4]

Solution for the problem.

  1. Create two iteration variables i and j and initialize it with values 0 and i+1 respectively
  2. Iterate over every element
  3. If value of an element nums[j] equals the value of target - nums[i] , return the indices i and j.

IMG-20210413-023019

In [14]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum

Implementing the solution

In [15]:
def twosum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if(nums[j] == target - nums[i]):
                return [i,j]
In [16]:
from jovian.pythondsa import evaluate_test_case
In [17]:
evaluate_test_case(twosum,test0)
Input: {'nums': [2, 4, 6, 8], 'target': 6} Expected Output: [0, 1] Actual Output: [0, 1] Execution Time: 0.005 ms Test Result: PASSED
Out[17]:
([0, 1], True, 0.005)
In [18]:
from jovian.pythondsa import evaluate_test_cases
In [19]:
evaluate_test_cases(twosum,tests)
TEST CASE #0 Input: {'nums': [2, 4, 6, 8], 'target': 6} Expected Output: [0, 1] Actual Output: [0, 1] Execution Time: 0.006 ms Test Result: PASSED TEST CASE #1 Input: {'nums': [], 'target': 2} Expected Output: None Actual Output: None Execution Time: 0.003 ms Test Result: PASSED TEST CASE #2 Input: {'nums': [1, 2, 4, 6, 8, 10], 'target': 11} Expected Output: [0, 5] Actual Output: [0, 5] Execution Time: 0.006 ms Test Result: PASSED TEST CASE #3 Input: {'nums': [12, 15, 17, 18], 'target': 28} Expected Output: None Actual Output: None Execution Time: 0.007 ms Test Result: PASSED TEST CASE #4 Input: {'nums': [0, 4, 6, 2, 9], 'target': 9} Expected Output: [0, 4] Actual Output: [0, 4] Execution Time: 0.005 ms Test Result: PASSED SUMMARY TOTAL: 5, PASSED: 5, FAILED: 0
Out[19]:
[([0, 1], True, 0.006),
 (None, True, 0.003),
 ([0, 5], True, 0.006),
 (None, True, 0.007),
 ([0, 4], True, 0.005)]
In [20]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum
In [ ]:
 

Complexity

There are two for loops which iterates over the elements. For each elementm we have to iterate over the remaining items in the list and hence it's time complexity is \(O(n^2)\) Space Complexity of the program remains constant. Hence space complexity = O(1)

In [21]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum

We can further reduce the time complexity of the algorithm by reducing the look up time by implementing a hash table and storing already discovered values inside it. By implementing a hash table, we can check during the iteration whether current element is already in the hash table and return it if it is found

In [22]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum

Solution for optimized version with less time complexity

Come with the optimized correct solution and explain it in simple words below:

  1. Create an empty hash table discovered

  2. iterate over the elements in the list

  3. Check if the value of target - nums[i] is already available in the discovered

  4. If it is already in discovered, return its value from discovered along with its index

  5. Otherwise, we have to store it into the hash table

Let's save and upload our work before continuing.

In [23]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum

Implementation

In [24]:
def twosum_optimized(nums, target):
    discovered = {}
    for i, num in enumerate(nums):
        if target - num in discovered:
            return([discovered[target - num], i])
        elif num not in discovered:
            discovered[num] = i
        
    
In [25]:
evaluate_test_case(twosum_optimized, test0)
Input: {'nums': [2, 4, 6, 8], 'target': 6} Expected Output: [0, 1] Actual Output: [0, 1] Execution Time: 0.009 ms Test Result: PASSED
Out[25]:
([0, 1], True, 0.009)
In [26]:
evaluate_test_cases(twosum_optimized, tests)
TEST CASE #0 Input: {'nums': [2, 4, 6, 8], 'target': 6} Expected Output: [0, 1] Actual Output: [0, 1] Execution Time: 0.008 ms Test Result: PASSED TEST CASE #1 Input: {'nums': [], 'target': 2} Expected Output: None Actual Output: None Execution Time: 0.003 ms Test Result: PASSED TEST CASE #2 Input: {'nums': [1, 2, 4, 6, 8, 10], 'target': 11} Expected Output: [0, 5] Actual Output: [0, 5] Execution Time: 0.005 ms Test Result: PASSED TEST CASE #3 Input: {'nums': [12, 15, 17, 18], 'target': 28} Expected Output: None Actual Output: None Execution Time: 0.003 ms Test Result: PASSED TEST CASE #4 Input: {'nums': [0, 4, 6, 2, 9], 'target': 9} Expected Output: [0, 4] Actual Output: [0, 4] Execution Time: 0.007 ms Test Result: PASSED SUMMARY TOTAL: 5, PASSED: 5, FAILED: 0
Out[26]:
[([0, 1], True, 0.008),
 (None, True, 0.003),
 ([0, 5], True, 0.005),
 (None, True, 0.003),
 ([0, 4], True, 0.007)]
In [27]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "nikhilcramakrishnan/twosum" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/nikhilcramakrishnan/twosum

Complexity analysis

Time complexity has been reduced to \(O(n)\). We have to travrese the list only one time, only one for loop is required and each lookup thereafter, takes only \(O(1)\) time.

Space complexity : \(O(n)\)

In [ ]:
jovian.commit()
[jovian] Attempting to save notebook..
Assignment Submission
In [ ]:
jovian.submit(assignment="pythondsa-project")
[jovian] Attempting to save notebook..