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

by

Objec­tive: 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:

  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 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.
  6. But for rest four elements, (6+4)/2= 5, (7+3)/2 = 5……(9+1)/2 = 5 which is our answer for local_max.
  7. 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.
  8. 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);
}
}

view raw
LocalMaxORMin.java
hosted with ❤ by GitHub


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

Related Posts: