Learn data science and machine learning by building real-world projects on Jovian

# NRnikhilcramakrishnan/twosum

5 months ago

## 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 ```
Out[21]:
``'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.

### 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

Output

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

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`.

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 ```
Out[14]:
``'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 ```
Out[20]:
``'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 ```
Out[21]:
``'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 ```
Out[22]:
``'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 ```
Out[23]:
``'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 ```
Out[27]:
``'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.. ```