JosephB
BAN USERI came up with two approaches/formulas to solve this problem, but first a couple clarifications; from the wording "Find the local max OR min" we can infer that there is only a single min or max, otherwise the problem would have said minima or maxima (plural form), also the "OR" states that there can be either one max or one min, but not both. It is not possible to locate multiple max/min in O(1) time. We also know from the "local" wording and the clarification that the max/min cannot be edge elements. Now with these conditions it is possible to solve this problem in O(1) time by using mathematical formulas.
Taking all conditions into consideration, the sequence of numbers must always consecutively increase, and then at some point (but only once) change direction to then consecutively decrease or vise versa. With that said, here are some valid, and invalid input examples:
Valid input:
12345432 (max = 5)
56789876543 (max = 9)
7656789 (min = 5)
98765456 (min = 4)
Invalid input:
123456 (the max/min is at an edge)
121212121 (contains 4 maxima and 3 minima)
121232121 (contains 2 local maxima, 1 global maxima and 2 minima)
54345454 (contains 1 global minima, 1 local minima and 2 maxima)
Legend:
f = the first number in the list (compared with last number and total numbers to find min/max)
l = the last number in the list (compared with first number and total numbers to find min/max)
n = the total/count of numbers in the list (needed to know the highest/lowest possible number)
s = the second number in the list (needed to determine increasing/decreasing trend, meaning that we are looking for the max/min)
a = the answer, which is either the local max or min (supporting input with only a single min or single max)
FORMULA #1:
This works by determining the highest/lowest possible max/min, and then subtracting from that based on the first and last numbers, which limit the max/min. The end result is a calculated max or min. Note that we use the first and second numbers to determine whether the numbers are increasing (looking for a max) or decreasing (looking for a min).
a = (2f - s + n(s - f)) + (|((2f - s + n(s - f)) - l)| / 2(f - s))
Note: Number enclosed within || means absolute value, example: |5| = |-5| = 5
(For a coded example see function "findCalculated")
This only looks complicated because it returns valid results for either a max or min, but if you separate them you would simply get:
Solve for max:
e = f + n - 1
a = e - (e - l) / 2
Solve for min:
e = f - n + 1
a = e + (e - l) / 2
Note: "e" means "extreme", it represents the highest/lowest possible max/min
FORMULA #2
This formula works differently and is a bit simpler, rather than calculating the logical max/min, it returns the expected index within the list, from which the max/min is to be read from. This formula also supports finding either a max or min.
a = |(n + (l - f)(s - f)) / 2|
(For a coded example see function "findPositional")
FINAL NOTES
There is a deficiency in both formulas, neither alerts of a problem when the max/min is an edge case, additionally they will both return incorrect results if the input sequence contains multiple maxima and/or minima. The first problem is easily solved in code by verifying that the result is not equal to either of the edges. The second problem is a bit trickier, however note that due to the behavior of these two formulas, they will both return different results given input with multiple minima/maxima; in my example below I actually use both of my formulas, and if they don't produce the same result then I know that we have invalid input with multiple maxima/minima.
Here is the code/verification using PHP:
<?php
class FindMaxMin
{
// Collects the results, and filters for common problems due to invalid input
// Input: $s = the numerical sequence for which we seek the local max or min
public static function find($s)
{
$n = count($s);
$a1 = self::findPositional($s, $n);
$a2 = self::findCalculated($s, $n);
if ($a1 != $a2)
return 'Multiple maxima/minima exist';
if ($a1 == $s[0] || $a1 == $s[$n - 1])
return 'No local max or min exists';
return ($a1 > $s[0] ? 'Local max is ' : 'Local min is ') . $a1;
}
// Finds the local max/min by calculated and querying its expected index within the list
// Input: $s = the numerical sequence, $n = the length of the sequence
private static function findPositional($s, $n)
{
// Formula: a = |(n + (l - f)(s - f)) / 2|
return $s[abs(($n + ($s[$n - 1] - $s[0]) * ($s[1] - $s[0])) / 2)];
}
// Finds the local max/min by calculating the highest/lowest possible max/min
// Input: $s = the numerical sequence, $n = the length of the sequence
private static function findCalculated($s, $n)
{
// Formula: a = (2f - s + n(s - f)) + (|((2f - s + n(s - f)) - l)| / 2(f - s))
return (2 * $s[0] - $s[1] + $n * ($s[1] - $s[0])) + (abs((2 * $s[0] - $s[1] + $n * ($s[1] - $s[0])) - $s[$n - 1]) / 2 * ($s[0] - $s[1]));
}
}
function main () {
// Generate test input
$input = [
[1, 2, 3, 4, 5, 4, 3, 2, 1],
[3, 4, 5, 6, 7, 8, 7, 6, 5],
[5, 6, 7, 8, 7, 6, 5, 4, 3],
[1, 2, 3, 4, 5],
[5, 4, 3, 2, 1],
[9, 8, 7, 6, 7, 8],
[3, 2, 1, 2, 3, 4, 5, 6, 7],
[7, 6, 5, 4, 3, 4, 5, 6, 7],
[1, 2, 1, 2, 1, 2, 1],
[1, 2, 1, 2, 3, 2, 1, 2, 1, 2],
[1, 2, 3, 4, 3, 2, 1, 0, -1, -2],
[3, 2, 1, 0, -1, -2, -1, 0, 1]
];
// Process input
foreach ($input as $sequence)
echo implode($sequence, ','), ' -> ', FindMaxMin::find($sequence), "\n";
}
main();
Here is the output:
1,2,3,4,5,4,3,2,1 -> Local max is 5
3,4,5,6,7,8,7,6,5 -> Local max is 8
5,6,7,8,7,6,5,4,3 -> Local max is 8
1,2,3,4,5 -> No local max or min exists
5,4,3,2,1 -> No local max or min exists
9,8,7,6,7,8 -> Local min is 6
3,2,1,2,3,4,5,6,7 -> Local min is 1
7,6,5,4,3,4,5,6,7 -> Local min is 3
1,2,1,2,1,2,1 -> Multiple maxima/minima exist
1,2,1,2,3,2,1,2,1,2 -> Multiple maxima/minima exist
1,2,3,4,3,2,1,0,-1,-2 -> Local max is 4
3,2,1,0,-1,-2,-1,0,1 -> Local min is -2
Here is my solution in PHP, water flows in reverse direction from outer oceans to identify intersections, flowing occurs through recursion:
- JosephB May 25, 2015