**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.
- Same logic will work for local_minimum.

**Code**:

**Output**:

[3, 4, 5, 4, 3, 2, 1, 0, -1]local maximum: 5
[-4, -5, -6, -5, -4, -3]local minimum: -6

Source: https://www.careercup.com/question?id=5113392333324288

__________________________________________________

**Top Companies Interview Questions..-**

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

__________________________________________________

### Like this:

Like Loading...

*Related*