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

Sign up to execute **find-the-index-of-peak-element-in-an-array** and 150,000+ data science projects. Build your own projects and share them online!

Updated 2 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 [1]:

`project_name = "Find_the_index_Of_peak_element_in_an_array" # give it an appropriate name`

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 "paullapee/find-the-index-of-peak-element-in-an-array" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/paullapee/find-the-index-of-peak-element-in-an-array
```

Find the index of the peak element in a given array

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 an array of integers. Find the index of the peak element in it. An array element is a peak if it is not smaller than its neighbours. For corner elements, we should consider only one neighbour.

**Input**

- An array e.g [4, 11, 18, 16]

**Output**

- The index of the pick element is 2 and the pick element is 18. It has 11 and 16 as neighbors

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 peak_element(nums):
pass
```

Save and upload your work before continuing.

In [6]:

`import jovian`

In [7]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "paullapee/find-the-index-of-peak-element-in-an-array" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/paullapee/find-the-index-of-peak-element-in-an-array
```

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:

**The input array has 3 elements in an ascending order****The input array has 6 elements in an ascending order and 2 repeated elements****The input array has 7 elements in an ascending order and 3 reapeated elements****The input array has 7 elements in an ascending order and 4 reapeated elements****The input array has 8 elements in an ascending order and 5 reapeated elements**

(add more if required)

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

```
# The input array has 3 elements in an ascending order
test0 = {
'input': {
'nums': [1,2,3,4,1],
},
'output': 3
}
```

In [9]:

```
# The input array has 6 elements in an ascending order and 2 repeated elements
test1 = {
'input': {
'nums': [1,2,3,4,5,6,2,2],
},
'output': 5
}
```

In [10]:

```
# The input array has 7 elements in an ascending order and 3 reapeated elements
test2 = {
'input': {
'nums': [1,2,3,4,5,6,7,3,3,3],
},
'output': 6
}
```

In [11]:

```
# The input array has 7 elements in an ascending order and 4 reapeated elements
test3 = {
'input': {
'nums': [1,2,3,4,5,6,7,4,4,4,4],
},
'output': 6
}
```

In [12]:

```
# The input array has 8 elements in an ascending order and 5 reapeated elements
test4 = {
'input': {
'nums': [1,2,3,4,5,6,7,8,5,5,5,5,5],
},
'output': 7
}
```

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

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:

**The solution will be to test all elements of the arrays to find the index of the peak element by running a linear search method****The method will detect if current number is less that the previous number and return the index of the maxima**

(add more steps if required)

Let's save and upload our work before continuing.

In [14]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "paullapee/find-the-index-of-peak-element-in-an-array" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/paullapee/find-the-index-of-peak-element-in-an-array
```

In [15]:

```
def peak_element(nums):
for i in range(1,len(nums)):
if (nums[i] >= nums[i - 1] and nums[i] >= nums[i + 1]) :
return i
```

In [16]:

`from jovian.pythondsa import evaluate_test_case`

In [17]:

`evaluate_test_case(peak_element, test0)`

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

Out[17]:

`(3, True, 0.006)`

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

function from `jovian`

.

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

(plural) function from `jovian`

.

In [18]:

`from jovian.pythondsa import evaluate_test_cases`

In [19]:

`evaluate_test_cases(peak_element, tests)`

```
TEST CASE #0
Input:
{'nums': [1, 2, 3, 4, 1]}
Expected Output:
3
Actual Output:
3
Execution Time:
0.004 ms
Test Result:
PASSED
TEST CASE #1
Input:
{'nums': [1, 2, 3, 4, 5, 6, 2, 2]}
Expected Output:
5
Actual Output:
5
Execution Time:
0.005 ms
Test Result:
PASSED
TEST CASE #2
Input:
{'nums': [1, 2, 3, 4, 5, 6, 7, 3, 3, 3]}
Expected Output:
6
Actual Output:
6
Execution Time:
0.007 ms
Test Result:
PASSED
TEST CASE #3
Input:
{'nums': [1, 2, 3, 4, 5, 6, 7, 4, 4, 4, 4]}
Expected Output:
6
Actual Output:
6
Execution Time:
0.004 ms
Test Result:
PASSED
TEST CASE #4
Input:
{'nums': [1, 2, 3, 4, 5, 6, 7, 8, 5, 5, 5, 5, 5]}
Expected Output:
7
Actual Output:
7
Execution Time:
0.003 ms
Test Result:
PASSED
SUMMARY
TOTAL: 5, PASSED: 5, FAILED: 0
```

Out[19]:

```
[(3, True, 0.004),
(5, True, 0.005),
(6, True, 0.007),
(6, True, 0.004),
(7, 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 [20]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "paullapee/find-the-index-of-peak-element-in-an-array" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/paullapee/find-the-index-of-peak-element-in-an-array
```

One traversal is needed for each array so the time complexity is O(n); n represents the size of the input

In [21]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "paullapee/find-the-index-of-peak-element-in-an-array" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/paullapee/find-the-index-of-peak-element-in-an-array
```

The linear search method appears to be inefficient. The efficient approach will be to use the divide and conquer method

that will find a peak in O(Logn)time

In [22]:

`jovian.commit()`

```
[jovian] Attempting to save notebook..
[jovian] Updating notebook "paullapee/find-the-index-of-peak-element-in-an-array" on https://jovian.ai
[jovian] Uploading notebook..
[jovian] Uploading additional files...
[jovian] Committed successfully! https://jovian.ai/paullapee/find-the-index-of-peak-element-in-an-array
```

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

**The problem can be easily solved in O(log(n)) time by using an idea similar to the binary search approach****The idea is to check is the middle element is the peak is the peak element of not.****If the middle element is not the peak element, we should check if the element of the right side is greater than the middle element****If the element on the left side is greater than the middle element, the peack element should be on the left side**

(add more steps if required)

Let's save and upload our work before continuing.

In [ ]:

`jovian.commit()`

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

In [ ]:

` `

In [3]:

```
def findPeakElement(nums):
start = 0
end = len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if nums[mid - 1] < nums[mid] and nums[mid] > nums[mid + 1]:
return mid
elif nums[mid - 1] > nums[mid]:
end = mid
elif nums[mid] < nums[mid + 1]:
start = mid
if nums[end] > nums[start]:
return end
```

In [ ]:

`from jovian.pythondsa import evaluate_test_cases`

In [ ]:

`evaluate_test_cases(findPeakElement, tests)`

The time compexity of the above solution is O(log(n))

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 [ ]:

` `

In [ ]:

` `