This post is completed by 1 user

  • 0
 Add to List
Medium

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

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:

  • The 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 the array is not allowed.
  • Every next element differs from the previous by +/- 1. We will use this property.
  • We will assume that the given array will have Either a local maximum OR local minimum and only one local maximum or only one local minimum is present.
  • Let’s consider that array has a local maximum, which means the array is first increasing and then decreasing.
  • Calculate the number which should have been the last element if the 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 the 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 the array could have been if the 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 the first 5 elements, which are the 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 the 5th element, in the actual array next element is decrement by 1, and in the array could have been, the next element is increment by 1. So adding those and dividing by 2 will give us the point from where it all started happening, which is our local maximum.
  8. The same logic will work for local_minimum.

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