Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Source: https://www.careercup.com/question?id=5113392333324288

You may also like...