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

Sign up to execute **pythondsa-project** and 160,000+ data science projects. Build your own projects and share them online!

Updated 5 months ago

*To learn how to use this template, check out the course "Data Structures and Algorithms in Python".*

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can *run* this tutorial and experiment with the code examples in a couple of ways: *using free online resources* (recommended) or *on your computer*.

The easiest way to start executing the code is to click the **Run** button at the top of this page and select **Run on Binder**. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the **Run** button at the top of this page, select the **Run Locally** option, and follow the instructions.

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [2]:

`project_name = "pythondsa-project" # give it an appropriate name`

In [3]:

`!pip install jovian --upgrade --quiet`

In [4]:

`import jovian`

In [ ]:

`jovian.commit(project=project_name)`

```
[jovian] Attempting to save notebook..
```

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Here's the systematic strategy we'll apply for solving problems:

- State the problem clearly. Identify the input & output formats.
- Come up with some example inputs & outputs. Try to cover all edge cases.
- Come up with a correct solution for the problem. State it in plain English.
- Implement the solution and test it using example inputs. Fix bugs, if any.
- Analyze the algorithm's complexity and identify inefficiencies, if any.
- Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

**Problem**

Given a list where it stores a series of integer. Start jumping from the first element, determine if we can jump to the end of list. The value in the list is the maximum hopping distance from that element.

**Input**

**nums:**List of maximum jumps from the element (positive integers only)

**Output**

**output:**boolean value stating if it is achievable

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

In [5]:

`from typing import *`

In [6]:

```
def canJump(nums: List[int]) -> bool:
pass
```

Save and upload your work before continuing.

In [7]:

`import jovian`

In [8]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "seanlimweisean/pythondsa-project" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/seanlimweisean/pythondsa-project
```

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:

**generic true case****generic false case****list with first value as zero****empty list****List with only value of 1****List with only 1 value**

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: `input`

(a dictionary itself containing one key for each argument to the function and `output`

(the expected result from the function).

In [9]:

```
test = {
'input': {
'nums': [2,3,1,1,4]
},
'output': True
}
```

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

.

In [10]:

`tests = []`

In [11]:

`tests.append(test)`

In [12]:

```
tests.append({
'input': {
'nums': [3,2,1,0,4]
},
'output': False
})
```

In [13]:

```
tests.append({
'input': {
'nums': [0,3,2,5,4]
},
'output': False
})
```

In [14]:

```
tests.append({
'input': {
'nums': []
},
'output': False
})
```

In [15]:

```
tests.append({
'input': {
'nums': [1,1,1,1,1]
},
'output': True
})
```

In [16]:

```
tests.append({
'input': {
'nums': [1]
},
'output': True
})
```

Our first goal should always be to come up with a *correct* solution to the problem, which may not necessarily be the most *efficient* solution. Come with a correct solution and explain it in simple words below:

**Let n being the length of the list nums and i as the index of the list nums****Special Case: If n is 0 or nums[0] is 0: return False****Special Case: If n is 1: return True****check if i+nums[i] is larger than the n-1, if so return True****else loop through j where j is from 1 to nums[i] and repeat step 4 for each i=i+j****if all iteration does not return True, return False instead**

Let's save and upload our work before continuing.

In [17]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "seanlimweisean/pythondsa-project" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/seanlimweisean/pythondsa-project
```

In [18]:

```
def canJump(nums: List[int]) -> bool:
if len(nums) == 0:
return False
if len(nums) == 1:
return True
def recurse(i:int):
max_jump = nums[i]
if(max_jump == 0):
return False
if i+max_jump >= len(nums) - 1:
return True
recurse_ans = False
for j in range(1, max_jump+1):
recurse_ans = recurse_ans or recurse(i+j)
return recurse_ans
return recurse(0)
```

We can test the function by passing the input to it directly or by using the `evaluate_test_case`

function from `jovian`

.

In [19]:

`from jovian.pythondsa import evaluate_test_case`

In [20]:

`evaluate_test_case(canJump, test)`

```
Input:
{'nums': [2, 3, 1, 1, 4]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.01 ms
Test Result:
PASSED
```

Out[20]:

`(True, True, 0.01)`

Evaluate your function against all the test cases together using the `evaluate_test_cases`

(plural) function from `jovian`

.

In [21]:

`from jovian.pythondsa import evaluate_test_cases`

In [22]:

`evaluate_test_cases(canJump, tests)`

```
TEST CASE #0
Input:
{'nums': [2, 3, 1, 1, 4]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.007 ms
Test Result:
PASSED
TEST CASE #1
Input:
{'nums': [3, 2, 1, 0, 4]}
Expected Output:
False
Actual Output:
False
Execution Time:
0.009 ms
Test Result:
PASSED
TEST CASE #2
Input:
{'nums': [0, 3, 2, 5, 4]}
Expected Output:
False
Actual Output:
False
Execution Time:
0.005 ms
Test Result:
PASSED
TEST CASE #3
Input:
{'nums': []}
Expected Output:
False
Actual Output:
False
Execution Time:
0.002 ms
Test Result:
PASSED
TEST CASE #4
Input:
{'nums': [1, 1, 1, 1, 1]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.008 ms
Test Result:
PASSED
TEST CASE #5
Input:
{'nums': [1]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.002 ms
Test Result:
PASSED
SUMMARY
TOTAL: 6, PASSED: 6, FAILED: 0
```

Out[22]:

```
[(True, True, 0.007),
(False, True, 0.009),
(False, True, 0.005),
(False, True, 0.002),
(True, True, 0.008),
(True, True, 0.002)]
```

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Let's save our work before continuing.

In [23]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "seanlimweisean/pythondsa-project" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/seanlimweisean/pythondsa-project
```

The tree of the recursion for test can be illustrated in the diagram below.

The worst case of this method is when each jump requires to loop through the whole remainder_list. In that case, the time complexity of this recursion solution is O(2

^{n}).

As recursion requires additional memory for the stack frame. The space complexity of the solution is O(n).

In [24]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "seanlimweisean/pythondsa-project" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/seanlimweisean/pythondsa-project
```

From the diagram above, we can see that there are repeat cases. Thus, we can use memoization to further reduce the time complexity of the solution.

In [25]:

```
def canJump(nums: List[int]) -> bool:
if len(nums) == 0:
return False
if len(nums) == 1:
return True
memo = {}
def recurse(i:int):
if memo.get(i) is not None:
return memo[i]
max_jump = nums[i]
if(max_jump == 0):
memo[i] = False
return memo[i]
if i+max_jump >= len(nums) - 1:
memo[i] = True
return memo[i]
memo[i] = False
for j in range(1, max_jump+1):
memo[i] = memo[i] or recurse(i+j)
return memo[i]
return recurse(0)
```

In [26]:

`evaluate_test_cases(canJump, tests)`

```
TEST CASE #0
Input:
{'nums': [2, 3, 1, 1, 4]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.011 ms
Test Result:
PASSED
TEST CASE #1
Input:
{'nums': [3, 2, 1, 0, 4]}
Expected Output:
False
Actual Output:
False
Execution Time:
0.013 ms
Test Result:
PASSED
TEST CASE #2
Input:
{'nums': [0, 3, 2, 5, 4]}
Expected Output:
False
Actual Output:
False
Execution Time:
0.006 ms
Test Result:
PASSED
TEST CASE #3
Input:
{'nums': []}
Expected Output:
False
Actual Output:
False
Execution Time:
0.002 ms
Test Result:
PASSED
TEST CASE #4
Input:
{'nums': [1, 1, 1, 1, 1]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.009 ms
Test Result:
PASSED
TEST CASE #5
Input:
{'nums': [1]}
Expected Output:
True
Actual Output:
True
Execution Time:
0.002 ms
Test Result:
PASSED
SUMMARY
TOTAL: 6, PASSED: 6, FAILED: 0
```

Out[26]:

```
[(True, True, 0.011),
(False, True, 0.013),
(False, True, 0.006),
(False, True, 0.002),
(True, True, 0.009),
(True, True, 0.002)]
```

With memoization, for each element in the array, it will only need to scan through all other element in its right. Thus the time complexity of the solution is O(n*(n-1))=O(n

^{2})

With memoization, addition memory space to store the result for each element is required, thus the space complexity is O(n+n)=O(2n)=O(n)

In [27]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "seanlimweisean/pythondsa-project" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/seanlimweisean/pythondsa-project
```

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

To further improve the solution, we can use a bottom-up method to remove the recursion. Rather than checking all jumps, we can calculate first index that is able to jump to the final index.

**Initialize the the required jump count to be n-1, where n is the length of the list nums****Let i be the index of the list nums, initialized i = n-2****if i + nums[i] is more or equal to the required jump count, update the required jump count to i****repeat step 2 and 3 until i = 0****Finally, if the required jump count is 0, return True else False**

In [ ]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
```

In [ ]:

```
def canJump(nums: List[int]) -> bool:
if len(nums)==0 or nums[0]==0: return False
if len(nums)==1: return True
requirement = len(nums) - 1
for i in range(len(nums)-2, -1, -1):
if i + nums[i] >= requirement:
requirement = i
return requirement == 0
```

In [ ]:

`evaluate_test_cases(canJump, tests)`

As this solution only require a single linear loop through the list nums, the time complexity of this solution is O(n).

As this solution only requires a extra constant memory space for requirements, the space complexity of the solution is O(1).

If you found the problem on an external platform, you can make a submission to test your solution.

Share your approach and start a discussion on the Jovian forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

In [ ]:

`jovian.commit()`

In [ ]:

```
jovian.submit(assignment="pythondsa-project")
```