**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,
and*last_should_be = first_element-(size-1)*.*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.

**Java Code**:

import java.util.Arrays; | |

public class LocalMaxORMin { | |

private static void find(int[] a) { | |

if(a==null||a.length==0){ | |

System.out.println("No Local maximum or minimum"); | |

return; | |

} | |

int size = a.length; | |

int first_element = a[0]; | |

int last_element = a[size–1]; | |

if(first_element+size–1==last_element || first_element–size+1==last_element){ | |

System.out.println("No Local maximum or minimum"); | |

return; | |

} | |

if(first_element<a[1]){ | |

//lets find local maximum | |

int last_should_be = first_element+(size–1); | |

int local_max = (last_should_be+last_element)/2; | |

System.out.println("local maximum: " + local_max); | |

}else{ | |

//lets find local maximum | |

int last_should_be = first_element–(size–1); | |

int local_min = (last_should_be+last_element)/2; | |

System.out.println("local minimum: " + local_min); | |

} | |

} | |

public static void main(String[] args) { | |

int a [] = {3,4,5,4,3,2,1,0,–1}; | |

System.out.print(Arrays.toString(a)); | |

find(a); | |

int b [] = {–4,–5,–6,–5,–4,–3}; | |

System.out.print(Arrays.toString(b)); | |

find(b); | |

} | |

} |

**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

Hi , Can we use below inputs ? it seems match the problem 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]

As mentioned in the approach it is assumed that only one local maximum OR only one local minimum is present

int c[] = {1, 2, 3, 4, 5, 4, 3, 2, 1,3}; //logic breaks

As mentioned in the approach it is assumed that only one local maximum OR only one local minimum is present

tutorialhorizon why