Objective: Given an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one more condition that the min or max should be non-edge elements of the array

Example:

1 2 3 4 5 4 3 2 1 -> Local maximum is 5
5 4 3 2 1 2 3 4 5 -> Local minimum is 1
1 2 3 4 5 -> No local max or min exists
5 4 3 2 1 -> No local max or min exists

Approach:

Problem is trivial in O(n) and can be solved in O(logn) using the technique in “Find local minina”.

We need to solve in O(1), which means traversing of array is not allowed.

Every next element differs from the previous by +/- 1. We will use this property.

We will assume that the give array will have Either local maximum OR local minimum and only one local maximum or only one local minimum is present.

Let’s consider that array has local maximum, means array is first increasing and then decreasing.

Calculate the number which should have been the last element if array is all increasing as last_should_be = first_element+(size-1)

Now local_max = (last_should_be+last_element)/2.

For local_minimum, last_should_be = first_element-(size-1) and local_min = (last_should_be+last_element)/2.

See the example below to understand why this equation works.

Handle the edge cases where array is all increasing or all decreasing, in that case there will be no local_max or local_min.

Example:

A[] = {1, 2, 3, 4, 5, 4, 3, 2, 1}

Now see what array could have been if array is all increasing.

{1, 2, 3, 4, 5, 6, 7, 8, 9}

{1, 2, 3, 4, 5, 4, 3, 2, 1} – Actual array

Observe first 5 elements, which are same. So if we calculate (1+1)/2 = 1, (2+2)/2 = 2, (3+3)/2 = 3, (4+4)/2 = 4 and (5+5)/2 = 5. Same as the element value.

But for rest four elements, (6+4)/2= 5, (7+3)/2 = 5……(9+1)/2 = 5 which is our answer for local_max.

Why because after 5th element, in actual array next element is decrement by 1 and in array could have been, next element is increment by 1. So adding those and divide by 2 will give us the point from where it all started happening, which is out local_maximum.

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________