Jovian
⭐️
Sign In

Data Structures and Algorithms 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 [1]:
project_name = "count number of occurrence of a number in a sorted list"
In [2]:
!pip install jovian --upgrade --quiet
In [3]:
import jovian
In [4]:
jovian.commit(project=project_name)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

Problem Statement

Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of the target element.

Source: https://leetcode.com/discuss/interview-question/124724/

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

We have been given a sorted list containing duplicates, we need to count the occurences of a given number(target element) and if the number is not found, report that as well.


Input

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

Output

  1. Element occurs 5 times

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

In [5]:
# Create a function signature here. The body of the function can contain a single statement: pass

def num_of_occurences():
    pass

Save and upload your work before continuing.

In [6]:
import jovian
In [7]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

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. A sorted list consisting of duplicates.
  2. The target element does not exist in the list.
  3. The list is empty.
  4. The target element occurs only once.
  5. The entire list is made up of duplicates of one element.

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 [8]:
test1 = {
    'input': {
        'nums' : [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target' : 5
    },
    'output': 5
}
In [9]:
test2 = {
    'input': {
        'nums' : [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target' : 3
    },
    'output': -1
}
In [10]:
test3 = {
    'input': {
        'nums' : [], 'target' : 5
    },
    'output': -1
}
In [11]:
test4 = {
    'input': {
        'nums' : [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target' : 2
    },
    'output': 1
}
In [12]:
test5 = {
    'input': {
        'nums' : [5, 5, 5, 5, 5,], 'target' : 5
    },
    'output': 5
}

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 = [test1, test2, test3, test4, test5]

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. The function will return the number of times the target element has occured in a sorted list.
  2. We will pass a sorted list and a target element into the function.
  3. if the target element is present in the sorted list, then the function will return the number of duplicates of the target element.
  4. if the list is empty, the function will return -1.
  5. if the list does not contain the target element, then function has to return -1.

Let's save and upload our work before continuing.

In [14]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

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

In [15]:
def num_of_occurences(nums ,target):
  
    count = 0
    nums_len = len(nums)
  
    if nums_len == 0:    #checking if the list is empty
        return -1
    elif nums_len != 0:
        for i in range(nums_len):
            if nums[i] == target:
                count = count+1       #increase the value of count everytime the target element is found
  
    if count != 0:       #checking if the element exists or not
        return count
    else:
        return -1
In [16]:
num_of_occurences(test1['input']['nums'], test1['input']['target'])
Out[16]:
5

We can test the function by passing the input to it directly or by using the evaluate_test_case function from jovian.

In [17]:
from jovian.pythondsa import evaluate_test_case
In [18]:
evaluate_test_case(num_of_occurences, test3)
Input: {'nums': [], 'target': 5} Expected Output: -1 Actual Output: -1 Execution Time: 0.003 ms Test Result: PASSED
Out[18]:
(-1, True, 0.003)

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [19]:
from jovian.pythondsa import evaluate_test_cases
In [20]:
evaluate_test_cases(num_of_occurences, tests)
TEST CASE #0 Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 5} Expected Output: 5 Actual Output: 5 Execution Time: 0.006 ms Test Result: PASSED TEST CASE #1 Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 3} Expected Output: -1 Actual Output: -1 Execution Time: 0.005 ms Test Result: PASSED TEST CASE #2 Input: {'nums': [], 'target': 5} Expected Output: -1 Actual Output: -1 Execution Time: 0.002 ms Test Result: PASSED TEST CASE #3 Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 2} Expected Output: 1 Actual Output: 1 Execution Time: 0.004 ms Test Result: PASSED TEST CASE #4 Input: {'nums': [5, 5, 5, 5, 5], 'target': 5} Expected Output: 5 Actual Output: 5 Execution Time: 0.003 ms Test Result: PASSED SUMMARY TOTAL: 5, PASSED: 5, FAILED: 0
Out[20]:
[(5, True, 0.006),
 (-1, True, 0.005),
 (-1, True, 0.002),
 (1, True, 0.004),
 (5, True, 0.003)]

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 [21]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

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

In [22]:
num_of_occurences_time_complexity = 'O(N)'
In [23]:
num_of_occurences_space_complexity = 'O(1)'
In [24]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

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

To deal with this problem in a more efficient way, we can use Binary Search.

The function will return the first and last occurences and then by subtracting the first occurence from the last occurence, the number of times the target element occured can be found.

In [25]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

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:

  1. We pass a sorted array (nums), target element and searchFirst which is used to specify whether we are looking for the first or last occurence of the target element.
  2. while left <= right we calculate mid and if the element is found, we return it as result.
  3. for determining whether it is the first occurence or the last, we use a if else statement, which if satisfied is the first occurence, else it will look for the last occurence of target element.
  4. We define another function search() which is used to call the binarysearch funtion twice to get the first and last occurence of the target element and calculate the number of times it has occurred by count = last - first.
  5. count == 0 and first != -1 and last != -1 is the condition if the element has occured only once.
  6. count != 0 and first != -1 and last != -1 if the target element has occurred more than once.
  7. else it retrns -1 which means either the list is empty or the target element does not exist.

Let's save and upload our work before continuing.

In [26]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/prashanthe31/count-number-of-occurrence-of-a-number-in-a-sorted-list

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

In [27]:
def binarySearch(nums, target, searchFirst):

    (left, right) = (0, len(nums) - 1)
 
    result = -1
    
    while left <= right:    
        mid = (left + right) // 2
        if target == nums[mid]:
            result = mid
            if searchFirst:
                right = mid - 1
            else:
                left = mid + 1
        elif target < nums[mid]:
            right = mid - 1
        else:
            left = mid + 1
 
    return result
In [28]:
def search(nums, target):
  
    count = 0
    first = binarySearch(nums, target, True)       
    last = binarySearch(nums, target, False)
    count = last - first
  
    #print(count)
    #print(first)
    #print(last)

    if count == 0 and first != -1 and last != -1:
        return count + 1
    elif count != 0 and first != -1 and last != -1:
        return count + 1
    else:
        return -1
In [29]:
search(test3['input']['nums'],test3['input']['target'] )
Out[29]:
-1
In [30]:
evaluate_test_case(search, test1)
Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 5} Expected Output: 5 Actual Output: 5 Execution Time: 0.007 ms Test Result: PASSED
Out[30]:
(5, True, 0.007)
In [31]:
evaluate_test_cases(search, tests)
TEST CASE #0 Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 5} Expected Output: 5 Actual Output: 5 Execution Time: 0.009 ms Test Result: PASSED TEST CASE #1 Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 3} Expected Output: -1 Actual Output: -1 Execution Time: 0.005 ms Test Result: PASSED TEST CASE #2 Input: {'nums': [], 'target': 5} Expected Output: -1 Actual Output: -1 Execution Time: 0.003 ms Test Result: PASSED TEST CASE #3 Input: {'nums': [1, 2, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7], 'target': 2} Expected Output: 1 Actual Output: 1 Execution Time: 0.005 ms Test Result: PASSED TEST CASE #4 Input: {'nums': [5, 5, 5, 5, 5], 'target': 5} Expected Output: 5 Actual Output: 5 Execution Time: 0.004 ms Test Result: PASSED SUMMARY TOTAL: 5, PASSED: 5, FAILED: 0
Out[31]:
[(5, True, 0.009),
 (-1, True, 0.005),
 (-1, True, 0.003),
 (1, True, 0.005),
 (5, True, 0.004)]

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

In [32]:
search_time_complexity = 'O(log(N))'
In [33]:
search_space_complexity = '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()
[jovian] Attempting to save notebook..
In [ ]: