# Find local minimum or local maximum in O(1).

Objec­tive: Given an array such that every next ele­ment dif­fers from the pre­vi­ous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The inter­viewer men­tioned one more con­di­tion that the min or max should be non-edge ele­ments of the array

Exam­ple:

```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:

• Prob­lem is triv­ial in O(n) and can be solved in O(logn) using the tech­nique in “Find local min­ina”.
• We need to solve in O(1), which means tra­vers­ing of array is not allowed.
• Every next ele­ment dif­fers from the pre­vi­ous by +/- 1. We will use this property.
• We will assume that the give array will have Either local max­i­mum OR local min­i­mum and only one local max­i­mum or only one local min­i­mum is present.
• Let’s con­sider that array has local max­i­mum, means array is first increas­ing and then decreasing.
• Cal­cu­late the num­ber which should have been the last ele­ment if array is all increas­ing 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 exam­ple below to under­stand why this equa­tion works.
• Han­dle the edge cases where array is all increas­ing or all decreas­ing, in that case there will be no local_max or local_min.

Exam­ple:

1. A[] = {1, 2, 3, 4, 5, 4, 3, 2, 1}
2. Now see what array could have been if array is all increasing.
3. {1, 2, 3, 4, 5, 6, 7, 8, 9}
4. {1, 2, 3, 4, 5, 4, 3, 2, 1} – Actual array
5. Observe first 5 ele­ments, which are same. So if we cal­cu­late (1+1)/2 = 1, (2+2)/2 = 2, (3+3)/2 = 3, (4+4)/2 = 4 and (5+5)/2 = 5. Same as the ele­ment value.
6. But for rest four ele­ments, (6+4)/2= 5, (7+3)/2 = 5……(9+1)/2 = 5 which is our answer for local_max.
7. Why because after 5th ele­ment, in actual array next ele­ment is decre­ment by 1 and in array could have been, next ele­ment is incre­ment by 1. So adding those and divide by 2 will give us the point from where it all started hap­pen­ing, which is out local_maximum.
8. Same logic will work for local_minimum.
Code:

Out­put:

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

#### You may also like...

• 陳孝庭

Hi , Can we use below inputs ? it seems match the prob­lem rules
A. [1, 2, 1, 2, 1, 2, 1]
B. [5, 4, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5]

• tuto­ri­al­hori­zon

As men­tioned in the approach it is assumed that only one local max­i­mum OR only one local min­i­mum is present