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:


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: