Jovian
⭐️
Sign In

Python DSA Course Project

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

How to run the code and save your work

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.

Option 1: Running using free online resources (1-click, recommended)

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.

Option 2: Running on your computer locally

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.

Saving your work

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

Problem Statement

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.

Source: https://leetcode.com/problems/jump-game/

The Method

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

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm's complexity and identify inefficiencies, if any.
  6. 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.

Solution

1. State the problem clearly. Identify the input & output formats.

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

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

Output

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

2. Come up with some example inputs & outputs. Try to cover all edge cases.

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. generic true case
  2. generic false case
  3. list with first value as zero
  4. empty list
  5. List with only value of 1
  6. 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
})

3. Come up with a correct solution for the problem. State it in plain English.

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:

  1. Let n being the length of the list nums and i as the index of the list nums
  2. Special Case: If n is 0 or nums[0] is 0: return False
  3. Special Case: If n is 1: return True
  4. check if i+nums[i] is larger than the n-1, if so return True
  5. else loop through j where j is from 1 to nums[i] and repeat step 4 for each i=i+j
  6. 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

4. Implement the solution and test it using example inputs. Fix bugs, if any.

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

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Complexity Analysis

Time Complexity

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(2n).

Space Complexity

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

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

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)]

Complexity Analysis

Time Complexity

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(n2)

Space Complexity

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

7. Come up with a correct solution for the problem. State it in plain English.

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.

  1. Initialize the the required jump count to be n-1, where n is the length of the list nums
  2. Let i be the index of the list nums, initialized i = n-2
  3. if i + nums[i] is more or equal to the required jump count, update the required jump count to i
  4. repeat step 2 and 3 until i = 0
  5. Finally, if the required jump count is 0, return True else False
In [ ]:
jovian.commit()
[jovian] Attempting to save notebook..

8. Implement the solution and test it using example inputs. Fix bugs, if any.

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)

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

Complexity Analysis

Time Complexity

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

Space Complexity

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()

Submission Project

In [ ]:
jovian.submit(assignment="pythondsa-project")