Find the element before which all the elements are smaller than it, and after which all are greater - GeeksforGeeks
Given an array, find an element before which all elements are smaller than it, and after which all are greater than it. Return index of the element if there is such an element, otherwise return -1.
Read full article from Find the element before which all the elements are smaller than it, and after which all are greater - GeeksforGeeks
Given an array, find an element before which all elements are smaller than it, and after which all are greater than it. Return index of the element if there is such an element, otherwise return -1.
An Efficient Solution can solve this problem in O(n) time using O(n) extra space. Below is detailed solution.
1) Create two arrays leftMax[] and rightMin[].
2) Traverse input array from left to right and fill leftMax[] such that leftMax[i] contains maximum element from 0 to i-1 in input array.
3) Traverse input array from right to left and fill rightMin[] such that rightMin[i] contains minimum element from to n-1 to i+1 in input array.
4) Traverse input array. For every element arr[i], check if arr[i] is greater than leftMax[i] and smaller than rightMin[i]. If yes, return i.
2) Traverse input array from left to right and fill leftMax[] such that leftMax[i] contains maximum element from 0 to i-1 in input array.
3) Traverse input array from right to left and fill rightMin[] such that rightMin[i] contains minimum element from to n-1 to i+1 in input array.
4) Traverse input array. For every element arr[i], check if arr[i] is greater than leftMax[i] and smaller than rightMin[i]. If yes, return i.
Further Optimization to above approach is to use only one extra array and traverse input array only twice. First traversal is same as above and fills leftMax[]. Next traversal traverses from right and keeps track of minimum. The second traversal also finds the required element.
int
findElement(
int
arr[],
int
n)
{
// leftMax[i] stores maximum of arr[0..i-1]
int
leftMax[n];
leftMax[0] = INT_MIN;
// Fill leftMax[]1..n-1]
for
(
int
i = 1; i < n; i++)
leftMax[i] = max(leftMax[i-1], arr[i-1]);
// Initialize minimum from right
int
rightMin = INT_MAX;
// Traverse array from right
for
(
int
i=n-1; i>=0; i--)
{
// Check if we found a required element
if
(leftMax[i] < arr[i] && rightMin > arr[i])
return
i;
// Update right minimum
rightMin = min(rightMin, arr[i]);
}
// If there was no element matching criteria
return
-1;
}
Read full article from Find the element before which all the elements are smaller than it, and after which all are greater - GeeksforGeeks