Find the highest peak in the mountain array.

Answer

This interview question concentrates on the developer's ability to work with Python search.

You are given an array of a mountain of size at least 3. Each element in the array represents the altitude of peaks in the mountain. There exists one peak in the array at index i such that
â— the peaks from index 0 to index i are in ascending order:
arr[0] < arr[1] < â€¦ < arr[i - 1] < arr[i]
â— and, the peaks from index i to index size - 1 are in descending order:-
arr[i] > arr[i + 1] > â€¦ > arr[size - 2] < arr[size - 1]

Your task is to find the index i of highest peak.

Example
â—	arr = [0, 1, 0]
expected output = 1
â—	arr = [0, 4, 2, 1]
expected output = 1

Solution:

Approach I (Linear search):

Traverse the array linearly and return the index of the element from where the array starts decreasing.

def findHighest(arr):
	n = len(arr)
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			return i

Time complexity- O(n)
Space complexity- O(1)

Approach II (Binary search):

Make a binary search and find whether at mid can we get the condition where the array starts decreasing. If yes then that is the index we are looking after.

def findHighest(arr):
	start = 0
	end = len(arr) - 1

	while start < end:
		mid = (start+end) // 2

		if arr[mid] < arr[mid + 1]:
			start = mid + 1
		else:
			end = mid
	return start

Time complexity- O(logn)
Space complexity- O(1)

Written by on May 21st, 2021

Next Question

How to Answer: Find the highest peak in the mountain array.

Advice and answer examples written specifically for a Python Beginner Level Binary Search job interview.

2. Find the highest peak in the mountain array.

This interview question concentrates on the developer's ability to work with Python search.

You are given an array of a mountain of size at least 3. Each element in the array represents the altitude of peaks in the mountain. There exists one peak in the array at index i such that
â— the peaks from index 0 to index i are in ascending order:
arr[0] < arr[1] < â€¦ < arr[i - 1] < arr[i]
â— and, the peaks from index i to index size - 1 are in descending order:-
arr[i] > arr[i + 1] > â€¦ > arr[size - 2] < arr[size - 1]

Your task is to find the index i of highest peak.

Example
â—	arr = [0, 1, 0]
expected output = 1
â—	arr = [0, 4, 2, 1]
expected output = 1

Solution:

Approach I (Linear search):

Traverse the array linearly and return the index of the element from where the array starts decreasing.

def findHighest(arr):
	n = len(arr)
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			return i

Time complexity- O(n)
Space complexity- O(1)

Approach II (Binary search):

Make a binary search and find whether at mid can we get the condition where the array starts decreasing. If yes then that is the index we are looking after.

def findHighest(arr):
	start = 0
	end = len(arr) - 1

	while start < end:
		mid = (start+end) // 2

		if arr[mid] < arr[mid + 1]:
			start = mid + 1
		else:
			end = mid
	return start

Time complexity- O(logn)
Space complexity- O(1)

Written by Jennie Taylor on May 21st, 2021

Next Question