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, 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:
- 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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