Local MinMax problem [reviewed]

Problem

Given the list of numbers, find the local min or local max

Local max or min is the number that exists between the first and last number.

For example,


1,2,3,4,3,2 => local max exists, which is 4

1,2,3,4,5,6,7 => No local max or local min exists

 5,4,3,2,1 => No local max or local min exists

 9,8,7,6,5,6,7,8,9 => local min exists, which is 5.

Challenging part is that your problem should run faster than O(N).



hint: all the numbers are increasing by 1 or decreasing by 1. There is no gap.

Here is the algorithm. There can be two cases that we need to consider.

1) Ascending numbers

No local min or max: The last number, A[N-1] should be the same as A[0] + N-1, where N is the length of the list.
 
     A[0] + N -1  = A[N-1]

If not, there must be local max.

In that case, the local min can be calculated by the following formula

  Local max = (A[0] + N-1 + A[N-1])/2

Figure 1. Local max

As shown in Figure 1. if the numbers ascends to the end. A[0] + N-1 will be same as A+B.
However, there exists a local max. the last number in the array in A[N-1] is the same as A-B.

Therefore, (A[0] + N-1 + A[N-1])/2 = (A+B + A - B)/2 = 2A/2, thereby getting A.


2) Descending numbers

No local min or max: The last number in the array, A[N-1] should be the same as A[0]-(N-1), where N is the length of the list.

    A[0] - (N-1) = A[N-1]

If not, there must be local min

In that case, the local min can be calculated by the following formula

  Local max = (A[0] + N-1 + A[N-1])/2

Figure 2. Local min

As shown in Figure 1. if the numbers descends to the end. A[0] - (N-1) will be same as -(A-B).
However, there exists a local min. the last number in the array in A[N-1] is the same as -A+B.

Therefore, (A[0] - N-1 + A[N-1])/2 = (-A-B - A + B)/2 = -2A/2, thereby getting -A.

Don't forget the fact that, A[0] > -A in the example.

Based on the algorithm discussed, the following implementation can be written.

	#include<iostream>
	using namespace std;
	void find_minmax(int *A, int len)
	{
	if (A[0] > A[1])
	{
	if ((A[0] - (len-1)) == A[len-1])
	{
	cout<< "No local min or max exist"<<endl;
	return;
	}
	int min = (A[0]-(len-1)+ A[len-1])/2;
	cout << "Local min : "<< min <<endl;
	} else {
	if ((A[0] + (len-1)) == A[len-1])
	{
	cout<<"No local min or max exists"<<endl;
	return;
	} else {
	int max = (A[0] + (len-1) + A[len-1])/2;
	cout <<"Local max : " << max << endl;
	}
	}
	}

view raw localminmax.cpp hosted with ❤ by GitHub

If look at the formula carefully, it will result in the max or min number when there is no local min or local max exists.

UPDATE(2019-08-01): solved the problem again using binary search, which is practically faster than $O(N)$. However, if the numbers between 0 and N-1 are either up-down or down-up V shape. The above algorithm will work and will be O(1). Need to look closer.

Here is the solution in python.

	class FindLocalMinMax:
	def find(self, list):
	self.min = None
	self.max = None
	first = list[0]
	last = list[-1]
	self.binary_search(list, 1, len(list) - 2, first, last)
	return [self.min, self.max]
	def binary_search(self, list, s, e, first, last):
	if s > e:
	return
	half = s + (e - s)//2
	# check for local min
	if list[half] < first and list[half] < last:
	if self.min == None or self.min > list[half]:
	self.min = list[half]
	# check for local max
	if list[half] > first and list[half] > last:
	if self.max == None or self.max < list[half]:
	self.max = list[half]
	# search both halves
	self.binary_search(list, s, half -1, first, last)
	self.binary_search(list, half + 1, e, first, last)
	finder = FindLocalMinMax()
	input = [1,2,3,4,3,2]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))
	input = [1,2,3,4,5,6,7]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))
	input = [5,4,3,2,1]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))
	input = [9,8,7,6,5,6,7,8,9]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))

view raw facebook_find_local_min_max_in_array_binary_search.py hosted with ❤ by GitHub

Practice statistics

10:00: to find the algorithm using a binary search
11:43: to write up the code and test case (No bug was found !!! yeah ...)
01:10: to write up test cases.

UPDATE(2019-08-01): Here is another solution running in $O(1)$ via simple computation to find the middle value.
This question could be just a brain teaser than algorithm question.

	# O(1)
	class FindLocalMinMax:
	def find(self, list):
	min = None
	max = None
	#ascending order but with V curve
	if len(list) > 2 and list[0] < list[1] and list[0] + len(list) -1 != list[-1]:
	local_max_pos = self.find_middle_value(list)
	max = list[local_max_pos]
	#descending order but with V curve
	if len(list) > 2 and list[0] > list[1] and list[0] - (len(list) - 1) != list[-1]:
	local_min_pos = self.find_middle_value(list)
	min = list[local_min_pos]
	return [min, max]
	def find_middle_value(self, list):
	#matching starting location to list[-1]
	matching_start = abs(list[0] - list[-1])
	last = len(list) - 1
	local_max = matching_start + (last - matching_start + 1)//2
	return local_max
	finder = FindLocalMinMax()
	input = [1,2,3,4,3,2]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))
	input = [1,2,3,4,5,6,7]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))
	input = [5,4,3,2,1]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))
	input = [9,8,7,6,5,6,7,8,9]
	result = finder.find(input)
	print("input = {} local min = {} local max = {}".format(input, result[0], result[1]))

view raw facebook_find_local_min_max_in_array_brain_teaser.py hosted with ❤ by GitHub

Practice statistics

10:00: to write the code with algorithm
02:00: to fix the logical error returning position instead of value and switching min and max